{"id":"81ca3f26-4c4a-4a36-8e0e-82931ec53853","name":"Linearize A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of linearize function. The function is expected to create a linear tree i.e. every node will have a single child only. For details check the question video.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n#include<climits>\nusing namespace std;\n\nclass Node\n\n{\n\npublic:\n\n int data = 0;\n\n vector<Node *> children;\n\n\n\n Node(int data)\n\n {\n\n this->data = data;\n\n }\n\n};\n\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" -> \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\n }\n}\n\nNode *constructor01(vector<int> &arr)\n\n{\n\n if (arr.size() == 0)\n\n return NULL;\n\n\n\n vector<Node *> stack;\n\n stack.push_back(new Node(arr[0]));\n\n\n\n Node *root = stack[0];\n\n\n\n for (int i = 1; i < arr.size(); i++)\n\n {\n\n if (arr[i] != -1)\n\n {\n\n Node *node = stack.back();\n\n Node *nnode = new Node(arr[i]);\n\n\n\n node->children.push_back(nnode);\n\n stack.push_back(nnode);\n\n }\n\n else\n\n stack.pop_back();\n\n }\n\n return root;\n\n}\n\nNode *linearize(Node *node)\n{\n// write code here\n}\n\nvoid solve()\n{\n int n;\n cin>>n;\n vector<int>arr(n);\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n Node * root=constructor01(arr);\n \n linearize(root);\n display(root);\n \n}\n\nint main()\n{\n solve();\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static int size(Node node) {\r\n int s = 0;\r\n\r\n for (Node child : node.children) {\r\n s += size(child);\r\n }\r\n s += 1;\r\n\r\n return s;\r\n }\r\n\r\n public static int max(Node node) {\r\n int m = Integer.MIN_VALUE;\r\n\r\n for (Node child : node.children) {\r\n int cm = max(child);\r\n m = Math.max(m, cm);\r\n }\r\n m = Math.max(m, node.data);\r\n\r\n return m;\r\n }\r\n\r\n public static int height(Node node) {\r\n int h = -1;\r\n\r\n for (Node child : node.children) {\r\n int ch = height(child);\r\n h = Math.max(h, ch);\r\n }\r\n h += 1;\r\n\r\n return h;\r\n }\r\n\r\n public static void traversals(Node node) {\r\n System.out.println(\"Node Pre \" + node.data);\r\n\r\n for (Node child : node.children) {\r\n System.out.println(\"Edge Pre \" + node.data + \"--\" + child.data);\r\n traversals(child);\r\n System.out.println(\"Edge Post \" + node.data + \"--\" + child.data);\r\n }\r\n\r\n System.out.println(\"Node Post \" + node.data);\r\n }\r\n\r\n public static void levelOrderLinewiseZZ(Node node) {\r\n Stack<Node> stack = new Stack<>();\r\n stack.add(node);\r\n\r\n Stack<Node> cstack = new Stack<>();\r\n int level = 0;\r\n\r\n while (stack.size() > 0) {\r\n node = stack.pop();\r\n System.out.print(node.data + \" \");\r\n\r\n if (level % 2 == 0) {\r\n for (int i = 0; i < node.children.size(); i++) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n } else {\r\n for (int i = node.children.size() - 1; i >= 0; i--) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n }\r\n\r\n if (stack.size() == 0) {\r\n stack = cstack;\r\n cstack = new Stack<>();\r\n level++;\r\n System.out.println();\r\n }\r\n }\r\n }\r\n\r\n public static void mirror(Node node) {\r\n for (Node child : node.children) {\r\n mirror(child);\r\n }\r\n Collections.reverse(node.children);\r\n }\r\n\r\n public static void removeLeaves(Node node) {\r\n for (int i = node.children.size() - 1; i >= 0; i--) {\r\n Node child = node.children.get(i);\r\n if (child.children.size() == 0) {\r\n node.children.remove(i);\r\n }\r\n }\r\n\r\n for(Node child: node.children){\r\n removeLeaves(child);\r\n }\r\n }\r\n\r\n public static void linearize(Node node){\r\n // write your code here\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n Node root = construct(arr);\r\n linearize(root);\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \n def _init_(self, key, children):\n \n self.key = key\n # self.child = []\n self.children=[]\n \n # Utility function to create a new tree node\ndef newNode(key): \n temp = Node()\n temp.key = key;\n # temp.child = []\n temp.children = []\n return temp\n \n \ndef display(root):\n s = \"\"\n s = str(root.key) + \" -> \"\n for child in root.children:\n s += str(child.key) + \", \"\n \n s += \".\" \n print(s)\n for child in root.children:\n display(child)\n# Prints the n-ary tree level wise\ndef constructor(lst,n):\n root = None\n stack = []\n for i in range(0,n):\n if lst[i]==-1:\n stack.pop()\n else:\n t= newNode(lst[i])\n if len(stack) > 0:\n stack[-1].children.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\ndef getTail(root):\n while len(root.children) == 1:\n root=root.children[0]\n return root \n\ndef linearize(root):\n # write your code here\nlst = []\n# number of elements as input\nn = int(input())\n# s1 =input().split()\n# values = input().split()\n\nlst = list(map(int, input().split()))\n \n\nroot = constructor(lst,n)\nlinearize(root)\ndisplay(root)"}},"points":10,"difficulty":"easy","sampleInput":"24\r\n10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1","sampleOutput":"10 -> 20, .\r\n20 -> 50, .\r\n50 -> 60, .\r\n60 -> 30, .\r\n30 -> 70, .\r\n70 -> 80, .\r\n80 -> 110, .\r\n110 -> 120, .\r\n120 -> 90, .\r\n90 -> 40, .\r\n40 -> 100, .\r\n100 -> .","questionVideo":"https://www.youtube.com/embed/SuPnlZacta0","hints":[],"associated":[{"id":"0b89fb7f-c688-4017-a09e-5b06c0c7690e","name":"In which order, are we linearizing a Generic Tree?","slug":"in-which-order-are-we-linearizing-a-generic-tree","type":4},{"id":"29e60398-bba8-48bf-8919-302c680a9dc9","name":"How many children every node will have after linearization of the generic tree?","slug":"how-many-children-every-node-will-have-after-linearization-of-the-generic-tree","type":4},{"id":"57650616-d786-4fbb-92c8-8d5a7a47e8f6","name":"What is the space complexity of approach to solve \"Linearize a Generic tree\"?","slug":"what-is-the-space-complexity-of-approach-to-solve-linearize-a-generic-tree","type":4},{"id":"c434adcd-651f-4bb4-bd32-2af73d10b5ae","name":"What is the time complexity of approach to solve \"Linearize a Generic tree\"?","slug":"what-is-the-time-complexity-of-approach-to-solve-linearize-a-generic-tree","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"6c3d94ed-cab4-4947-b281-9aecf5e49b41","name":"Linearize A Generic Tree","slug":"linearize-a-generic-tree","type":1}],"next":{"id":"940f624d-bfbc-468d-aae9-d1ea99a3111b","name":"Linearize A Generic Tree","type":3,"slug":"linearize-a-generic-tree"},"prev":{"id":"6edf26fe-c378-4244-93f6-705d85bf5942","name":"Remove Leaves in Generic Tree","type":3,"slug":"remove-leaves-in-generic-tree"}}}

Linearize A Generic Tree

1. You are given a partially written GenericTree class. 2. You are required to complete the body of linearize function. The function is expected to create a linear tree i.e. every node will have a single child only. For details check the question video. 3. Input and Output is managed for you.

{"id":"81ca3f26-4c4a-4a36-8e0e-82931ec53853","name":"Linearize A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of linearize function. The function is expected to create a linear tree i.e. every node will have a single child only. For details check the question video.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n#include<climits>\nusing namespace std;\n\nclass Node\n\n{\n\npublic:\n\n int data = 0;\n\n vector<Node *> children;\n\n\n\n Node(int data)\n\n {\n\n this->data = data;\n\n }\n\n};\n\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" -> \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\n }\n}\n\nNode *constructor01(vector<int> &arr)\n\n{\n\n if (arr.size() == 0)\n\n return NULL;\n\n\n\n vector<Node *> stack;\n\n stack.push_back(new Node(arr[0]));\n\n\n\n Node *root = stack[0];\n\n\n\n for (int i = 1; i < arr.size(); i++)\n\n {\n\n if (arr[i] != -1)\n\n {\n\n Node *node = stack.back();\n\n Node *nnode = new Node(arr[i]);\n\n\n\n node->children.push_back(nnode);\n\n stack.push_back(nnode);\n\n }\n\n else\n\n stack.pop_back();\n\n }\n\n return root;\n\n}\n\nNode *linearize(Node *node)\n{\n// write code here\n}\n\nvoid solve()\n{\n int n;\n cin>>n;\n vector<int>arr(n);\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n Node * root=constructor01(arr);\n \n linearize(root);\n display(root);\n \n}\n\nint main()\n{\n solve();\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static int size(Node node) {\r\n int s = 0;\r\n\r\n for (Node child : node.children) {\r\n s += size(child);\r\n }\r\n s += 1;\r\n\r\n return s;\r\n }\r\n\r\n public static int max(Node node) {\r\n int m = Integer.MIN_VALUE;\r\n\r\n for (Node child : node.children) {\r\n int cm = max(child);\r\n m = Math.max(m, cm);\r\n }\r\n m = Math.max(m, node.data);\r\n\r\n return m;\r\n }\r\n\r\n public static int height(Node node) {\r\n int h = -1;\r\n\r\n for (Node child : node.children) {\r\n int ch = height(child);\r\n h = Math.max(h, ch);\r\n }\r\n h += 1;\r\n\r\n return h;\r\n }\r\n\r\n public static void traversals(Node node) {\r\n System.out.println(\"Node Pre \" + node.data);\r\n\r\n for (Node child : node.children) {\r\n System.out.println(\"Edge Pre \" + node.data + \"--\" + child.data);\r\n traversals(child);\r\n System.out.println(\"Edge Post \" + node.data + \"--\" + child.data);\r\n }\r\n\r\n System.out.println(\"Node Post \" + node.data);\r\n }\r\n\r\n public static void levelOrderLinewiseZZ(Node node) {\r\n Stack<Node> stack = new Stack<>();\r\n stack.add(node);\r\n\r\n Stack<Node> cstack = new Stack<>();\r\n int level = 0;\r\n\r\n while (stack.size() > 0) {\r\n node = stack.pop();\r\n System.out.print(node.data + \" \");\r\n\r\n if (level % 2 == 0) {\r\n for (int i = 0; i < node.children.size(); i++) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n } else {\r\n for (int i = node.children.size() - 1; i >= 0; i--) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n }\r\n\r\n if (stack.size() == 0) {\r\n stack = cstack;\r\n cstack = new Stack<>();\r\n level++;\r\n System.out.println();\r\n }\r\n }\r\n }\r\n\r\n public static void mirror(Node node) {\r\n for (Node child : node.children) {\r\n mirror(child);\r\n }\r\n Collections.reverse(node.children);\r\n }\r\n\r\n public static void removeLeaves(Node node) {\r\n for (int i = node.children.size() - 1; i >= 0; i--) {\r\n Node child = node.children.get(i);\r\n if (child.children.size() == 0) {\r\n node.children.remove(i);\r\n }\r\n }\r\n\r\n for(Node child: node.children){\r\n removeLeaves(child);\r\n }\r\n }\r\n\r\n public static void linearize(Node node){\r\n // write your code here\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n Node root = construct(arr);\r\n linearize(root);\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \n def _init_(self, key, children):\n \n self.key = key\n # self.child = []\n self.children=[]\n \n # Utility function to create a new tree node\ndef newNode(key): \n temp = Node()\n temp.key = key;\n # temp.child = []\n temp.children = []\n return temp\n \n \ndef display(root):\n s = \"\"\n s = str(root.key) + \" -> \"\n for child in root.children:\n s += str(child.key) + \", \"\n \n s += \".\" \n print(s)\n for child in root.children:\n display(child)\n# Prints the n-ary tree level wise\ndef constructor(lst,n):\n root = None\n stack = []\n for i in range(0,n):\n if lst[i]==-1:\n stack.pop()\n else:\n t= newNode(lst[i])\n if len(stack) > 0:\n stack[-1].children.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\ndef getTail(root):\n while len(root.children) == 1:\n root=root.children[0]\n return root \n\ndef linearize(root):\n # write your code here\nlst = []\n# number of elements as input\nn = int(input())\n# s1 =input().split()\n# values = input().split()\n\nlst = list(map(int, input().split()))\n \n\nroot = constructor(lst,n)\nlinearize(root)\ndisplay(root)"}},"points":10,"difficulty":"easy","sampleInput":"24\r\n10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1","sampleOutput":"10 -> 20, .\r\n20 -> 50, .\r\n50 -> 60, .\r\n60 -> 30, .\r\n30 -> 70, .\r\n70 -> 80, .\r\n80 -> 110, .\r\n110 -> 120, .\r\n120 -> 90, .\r\n90 -> 40, .\r\n40 -> 100, .\r\n100 -> .","questionVideo":"https://www.youtube.com/embed/SuPnlZacta0","hints":[],"associated":[{"id":"0b89fb7f-c688-4017-a09e-5b06c0c7690e","name":"In which order, are we linearizing a Generic Tree?","slug":"in-which-order-are-we-linearizing-a-generic-tree","type":4},{"id":"29e60398-bba8-48bf-8919-302c680a9dc9","name":"How many children every node will have after linearization of the generic tree?","slug":"how-many-children-every-node-will-have-after-linearization-of-the-generic-tree","type":4},{"id":"57650616-d786-4fbb-92c8-8d5a7a47e8f6","name":"What is the space complexity of approach to solve \"Linearize a Generic tree\"?","slug":"what-is-the-space-complexity-of-approach-to-solve-linearize-a-generic-tree","type":4},{"id":"c434adcd-651f-4bb4-bd32-2af73d10b5ae","name":"What is the time complexity of approach to solve \"Linearize a Generic tree\"?","slug":"what-is-the-time-complexity-of-approach-to-solve-linearize-a-generic-tree","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"6c3d94ed-cab4-4947-b281-9aecf5e49b41","name":"Linearize A Generic Tree","slug":"linearize-a-generic-tree","type":1}],"next":{"id":"940f624d-bfbc-468d-aae9-d1ea99a3111b","name":"Linearize A Generic Tree","type":3,"slug":"linearize-a-generic-tree"},"prev":{"id":"6edf26fe-c378-4244-93f6-705d85bf5942","name":"Remove Leaves in Generic Tree","type":3,"slug":"remove-leaves-in-generic-tree"}}}
plane

Editor

Loading...

Linearize A Generic Tree

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of linearize function. The function is expected to create a linear tree i.e. every node will have a single child only. For details check the question video. 3. Input and Output is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

Sample Output

10 -> 20, . 20 -> 50, . 50 -> 60, . 60 -> 30, . 30 -> 70, . 70 -> 80, . 80 -> 110, . 110 -> 120, . 120 -> 90, . 90 -> 40, . 40 -> 100, . 100 -> .

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode