{"id":"dde9d2d6-ad1c-4cb1-b0a5-0b74b026df9a","name":"Levelorder Linewise (generic Tree)","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of levelorderLineWise function. The function is expected to visit every node in \"levelorder fashion\" and print them from left to right (level by level). All nodes on same level should be separated by a space. Different levels should be on separate lines. Please check the question video for more details.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"All nodes from left to right (level by level) all separated by a space.\r\nAll levels on separate lines starting from top to bottom.","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 levelOrderLinewise(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 levelOrderLinewise(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 \r\n20 30 40 \r\n50 60 70 80 90 100 \r\n110 120","questionVideo":"https://www.youtube.com/embed/t4ts_6m4z68","hints":[],"associated":[{"id":"0bea3421-3837-4f41-a12d-a233cd740c9a","name":"What is the space complexity of level order linewise traversal in a tree?","slug":"what-is-the-space-complexity-of-level-order-linewise-traversal-in-a-tree","type":4},{"id":"4d6f80c7-4ade-48fd-bd1f-50b87988a473","name":"Level order traversal of a tree is formed with the help of","slug":"level-order-traversal-of-a-tree-is-formed-with-the-help-of","type":4},{"id":"c7b45106-6a11-4618-8ea7-37626ea4c7aa","name":"What is the time complexity of level order traversal?","slug":"what-is-the-time-complexity-of-level-order-traversal","type":4},{"id":"e5859b14-1226-4a8c-b4d5-182e5cce26d0","name":"Which of the following graph traversals closely imitates level order traversal of a binary tree?","slug":"which-of-the-following-graph-traversals-closely-imitates-level-order-traversal-of-a-binary-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":"8dccc5f0-1e07-424e-8b6e-30efa01c6a6b","name":"Levelorder Linewise (generic Tree)","slug":"levelorder-linewise-generic-tree","type":1}],"next":{"id":"d10b9bcf-aea8-43fc-803c-d791081d4079","name":"Level Order-Line Wise","type":3,"slug":"level-order-line-wise"},"prev":{"id":"7524f7aa-6534-4a0c-9031-394d6bec8f70","name":"Level Order of Generic Tree","type":3,"slug":"level-order-of-generic-tree"}}}

Levelorder Linewise (generic Tree)

1. You are given a partially written GenericTree class. 2. You are required to complete the body of levelorderLineWise function. The function is expected to visit every node in "levelorder fashion" and print them from left to right (level by level). All nodes on same level should be separated by a space. Different levels should be on separate lines. Please check the question video for more details. 3. Input is managed for you.

{"id":"dde9d2d6-ad1c-4cb1-b0a5-0b74b026df9a","name":"Levelorder Linewise (generic Tree)","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of levelorderLineWise function. The function is expected to visit every node in \"levelorder fashion\" and print them from left to right (level by level). All nodes on same level should be separated by a space. Different levels should be on separate lines. Please check the question video for more details.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"All nodes from left to right (level by level) all separated by a space.\r\nAll levels on separate lines starting from top to bottom.","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 levelOrderLinewise(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 levelOrderLinewise(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 \r\n20 30 40 \r\n50 60 70 80 90 100 \r\n110 120","questionVideo":"https://www.youtube.com/embed/t4ts_6m4z68","hints":[],"associated":[{"id":"0bea3421-3837-4f41-a12d-a233cd740c9a","name":"What is the space complexity of level order linewise traversal in a tree?","slug":"what-is-the-space-complexity-of-level-order-linewise-traversal-in-a-tree","type":4},{"id":"4d6f80c7-4ade-48fd-bd1f-50b87988a473","name":"Level order traversal of a tree is formed with the help of","slug":"level-order-traversal-of-a-tree-is-formed-with-the-help-of","type":4},{"id":"c7b45106-6a11-4618-8ea7-37626ea4c7aa","name":"What is the time complexity of level order traversal?","slug":"what-is-the-time-complexity-of-level-order-traversal","type":4},{"id":"e5859b14-1226-4a8c-b4d5-182e5cce26d0","name":"Which of the following graph traversals closely imitates level order traversal of a binary tree?","slug":"which-of-the-following-graph-traversals-closely-imitates-level-order-traversal-of-a-binary-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":"8dccc5f0-1e07-424e-8b6e-30efa01c6a6b","name":"Levelorder Linewise (generic Tree)","slug":"levelorder-linewise-generic-tree","type":1}],"next":{"id":"d10b9bcf-aea8-43fc-803c-d791081d4079","name":"Level Order-Line Wise","type":3,"slug":"level-order-line-wise"},"prev":{"id":"7524f7aa-6534-4a0c-9031-394d6bec8f70","name":"Level Order of Generic Tree","type":3,"slug":"level-order-of-generic-tree"}}}
plane

Editor


Loading...

Levelorder Linewise (generic Tree)

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of levelorderLineWise function. The function is expected to visit every node in "levelorder fashion" and print them from left to right (level by level). All nodes on same level should be separated by a space. Different levels should be on separate lines. Please check the question video for more details. 3. Input is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

All nodes from left to right (level by level) all separated by a space. All levels on separate lines starting from top to bottom.

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 30 40 50 60 70 80 90 100 110 120

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode