{"id":"560aae66-54ff-4225-9645-4595973d5c6c","name":"Levelorder Traversal Of Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of levelorder function. The function is expected to print tree level by level, left to right. Each level must be on a separate line and elements of same level should be separated by space\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Each level must be on a separate line and elements of same level should be separated by space","constraints":"None","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<string.h>\n#include<vector>\n#include<queue>\n\nusing namespace std;\nclass Node{\npublic:\n int data;\n Node* left = nullptr;\n Node* right = nullptr;\n Node(int data){\n this->data = data;\n }\n};\n\nclass Pair {\npublic:\n Node* node = nullptr;\n int state = 0;\n Pair(Node* node, int state) {\n this->node = node;\n this->state = state;\n }\n};\n\nint idx = 0;\nNode* constructTree(vector<int>& arr){\n if (idx == arr.size() || arr[idx] == -1){\n idx++;\n return nullptr;\n }Node* node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvoid display(Node* node){\n if (node == nullptr)\n return;\n string str = \"\";\n str += node->left != nullptr ? to_string(node->left->data) : \".\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right != nullptr ? to_string(node->right->data) : \".\";\n cout << str << endl;\n display(node->left);\n display(node->right);\n}\n\n\nvoid levelOrder(Node* node) {\n // write your code here\n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for (int i = 0; i < n; i++) {\n string temp;\n cin >> temp;\n if (temp == \"n\"){\n arr[i] = -1;\n }else{\n arr[i] = stoi(temp);\n }\n }\n Node* root = constructTree(arr);\n levelOrder(root);\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static void levelOrder(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 Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n levelOrder(root);\r\n }\r\n\r\n}"},"python":{"code":"import queue\nclass Node:\n \n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n \n\ndef level(node):\n #write your code here\n \n \nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\n\nroot = construct(arr)\nlevel(root)"}},"points":10,"difficulty":"easy","sampleInput":"19\r\n50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n","sampleOutput":"50 \r\n25 75 \r\n12 37 62 87 \r\n30 70","questionVideo":"https://www.youtube.com/embed/u0maCj0o_LY","hints":[],"associated":[{"id":"e6dd8f4c-e8e4-41cf-974c-32ab82b40b97","name":"The elements in pre order traversal of a binary search tree is always sorted. Is it True or false?","slug":"the-elements-in-pre-order-traversal-of-a-binary-search-tree-is-always-sorted-is-it-true-or-false","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":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"fb7cc821-059c-4f2d-a8f8-00544be0375e","name":"Levelorder Traversal Of Binary Tree","slug":"levelorder-traversal-of-binary-tree","type":1}],"next":{"id":"55fadc18-9c8c-41f1-9717-bbcdb4d991a0","name":"Level Order Traversal Of Binary Tree","type":3,"slug":"level-order-traversal-of-binary-tree"},"prev":{"id":"19aa94b1-b3c3-434a-bafc-240c0b6c8165","name":"Traversal in a Binary Tree","type":0,"slug":"traversal-in-a-binary-tree"}}}

Levelorder Traversal Of Binary Tree

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of levelorder function. The function is expected to print tree level by level, left to right. Each level must be on a separate line and elements of same level should be separated by space 3. Input is managed for you.

{"id":"560aae66-54ff-4225-9645-4595973d5c6c","name":"Levelorder Traversal Of Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of levelorder function. The function is expected to print tree level by level, left to right. Each level must be on a separate line and elements of same level should be separated by space\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Each level must be on a separate line and elements of same level should be separated by space","constraints":"None","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<string.h>\n#include<vector>\n#include<queue>\n\nusing namespace std;\nclass Node{\npublic:\n int data;\n Node* left = nullptr;\n Node* right = nullptr;\n Node(int data){\n this->data = data;\n }\n};\n\nclass Pair {\npublic:\n Node* node = nullptr;\n int state = 0;\n Pair(Node* node, int state) {\n this->node = node;\n this->state = state;\n }\n};\n\nint idx = 0;\nNode* constructTree(vector<int>& arr){\n if (idx == arr.size() || arr[idx] == -1){\n idx++;\n return nullptr;\n }Node* node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvoid display(Node* node){\n if (node == nullptr)\n return;\n string str = \"\";\n str += node->left != nullptr ? to_string(node->left->data) : \".\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right != nullptr ? to_string(node->right->data) : \".\";\n cout << str << endl;\n display(node->left);\n display(node->right);\n}\n\n\nvoid levelOrder(Node* node) {\n // write your code here\n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for (int i = 0; i < n; i++) {\n string temp;\n cin >> temp;\n if (temp == \"n\"){\n arr[i] = -1;\n }else{\n arr[i] = stoi(temp);\n }\n }\n Node* root = constructTree(arr);\n levelOrder(root);\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n public static void levelOrder(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 Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n levelOrder(root);\r\n }\r\n\r\n}"},"python":{"code":"import queue\nclass Node:\n \n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n \n\ndef level(node):\n #write your code here\n \n \nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\n\nroot = construct(arr)\nlevel(root)"}},"points":10,"difficulty":"easy","sampleInput":"19\r\n50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n","sampleOutput":"50 \r\n25 75 \r\n12 37 62 87 \r\n30 70","questionVideo":"https://www.youtube.com/embed/u0maCj0o_LY","hints":[],"associated":[{"id":"e6dd8f4c-e8e4-41cf-974c-32ab82b40b97","name":"The elements in pre order traversal of a binary search tree is always sorted. Is it True or false?","slug":"the-elements-in-pre-order-traversal-of-a-binary-search-tree-is-always-sorted-is-it-true-or-false","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":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"fb7cc821-059c-4f2d-a8f8-00544be0375e","name":"Levelorder Traversal Of Binary Tree","slug":"levelorder-traversal-of-binary-tree","type":1}],"next":{"id":"55fadc18-9c8c-41f1-9717-bbcdb4d991a0","name":"Level Order Traversal Of Binary Tree","type":3,"slug":"level-order-traversal-of-binary-tree"},"prev":{"id":"19aa94b1-b3c3-434a-bafc-240c0b6c8165","name":"Traversal in a Binary Tree","type":0,"slug":"traversal-in-a-binary-tree"}}}
plane

Editor

Loading...

Levelorder Traversal Of Binary Tree

easy

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of levelorder function. The function is expected to print tree level by level, left to right. Each level must be on a separate line and elements of same level should be separated by space 3. Input is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Each level must be on a separate line and elements of same level should be separated by space

Example

Sample Input

19 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n

Sample Output

50 25 75 12 37 62 87 30 70

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode