`{"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"}}}`

Editor

# 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.

None

## Format

### Input

Input is managed for you

### Output

Output is managed for you

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}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

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}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