{"id":"8d7ff37f-8d75-4f4b-97b6-2b5a6c2d07b1","name":"Iterative Pre, Post And Inorder Traversals Of Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of iterativePrePostInTraversal function. The function is expected to print pre order, in order and post order of the tree in separate lines (first pre, then in and finally post order). All elements in an order must be separated by a space.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"pre order (elements separated by space)\r\nin order (elements separated by space)\r\npost order (elements separated by space)","constraints":"None","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<string.h>\n#include<vector>\n#include<queue>\n#include<stack>\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\nNode* construct(vector<int>& arr) {\n Node* root = new Node(arr[0]);\n pair<Node*, int> p = {root, 1};\n\n stack<pair<Node*, int>> st;\n st.push(p);\n\n int idx = 1;\n while (!st.empty()) {\n if (st.top().second == 1) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->left = new Node(arr[idx]);\n pair<Node*, int> lp = {st.top().first->left, 1};\n st.push(lp);\n }\n else {\n st.top().first->left = nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*, int> rp = {st.top().first->right, 1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n }\n return root;\n}\n\n\nvoid iterativePrePostInTraversal(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 = construct(arr);\n iterativePrePostInTraversal(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 iterativePrePostInTraversal(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 iterativePrePostInTraversal(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\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 \n \n \ndef iterativePrePostInTraversal(node):\n # write your code here\n \n \n\nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\n\nroot = construct(arr)\niterativePrePostInTraversal(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 25 12 37 30 75 62 70 87 \r\n12 25 30 37 50 62 70 75 87 \r\n12 30 37 25 70 62 87 75 50","questionVideo":"https://www.youtube.com/embed/d97z0fGBjpE","hints":[],"associated":[{"id":"204408f3-6b6f-4d09-9a0d-7aacf3699e00","name":"What is In Order of this Binary Tree - 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n ?","slug":"what-is-in-order-of-this-binary-tree-50-25-12-n-n-37-30-n-n-n-75-62-n-70-n-n-87-n-n","type":4},{"id":"6a8dc66e-d234-4f1e-a998-512456b40c23","name":"What is the Time Complexity of \"Iterative Pre, post and Inorder\"?","slug":"what-is-the-time-complexity-of-iterative-pre-post-and-inorder","type":4},{"id":"70b2ce6b-5f5b-4239-9328-ca7f0816b653","name":"What is Pre Order of this Binary Tree - 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n ?","slug":"what-is-pre-order-of-this-binary-tree-50-25-12-n-n-37-30-n-n-n-75-62-n-70-n-n-87-n-n","type":4},{"id":"ebbb7535-9a85-49c0-a15f-64e0dfa42607","name":"What is Post Order of this Binary Tree - 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n ?","slug":"what-is-post-order-of-this-binary-tree-50-25-12-n-n-37-30-n-n-n-75-62-n-70-n-n-87-n-n","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":"706f5513-c79d-43f2-9ee2-625dc215b138","name":"Iterative Pre, Post And Inorder Traversals Of Binary Tree","slug":"iterative-pre-post-and-inorder-traversals-of-binary-tree","type":1}],"next":{"id":"95f01142-a60f-4a99-a388-e19d3d0c6a47","name":"Iterative Pre, Post And Inorder In Binary Tree","type":3,"slug":"iterative-pre-post-and-inorder-in-binary-tree"},"prev":{"id":"55fadc18-9c8c-41f1-9717-bbcdb4d991a0","name":"Level Order Traversal Of Binary Tree","type":3,"slug":"level-order-traversal-of-binary-tree"}}}

Iterative Pre, Post And Inorder Traversals Of Binary Tree

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of iterativePrePostInTraversal function. The function is expected to print pre order, in order and post order of the tree in separate lines (first pre, then in and finally post order). All elements in an order must be separated by a space. 3. Input is managed for you.

{"id":"8d7ff37f-8d75-4f4b-97b6-2b5a6c2d07b1","name":"Iterative Pre, Post And Inorder Traversals Of Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of iterativePrePostInTraversal function. The function is expected to print pre order, in order and post order of the tree in separate lines (first pre, then in and finally post order). All elements in an order must be separated by a space.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"pre order (elements separated by space)\r\nin order (elements separated by space)\r\npost order (elements separated by space)","constraints":"None","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<string.h>\n#include<vector>\n#include<queue>\n#include<stack>\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\nNode* construct(vector<int>& arr) {\n Node* root = new Node(arr[0]);\n pair<Node*, int> p = {root, 1};\n\n stack<pair<Node*, int>> st;\n st.push(p);\n\n int idx = 1;\n while (!st.empty()) {\n if (st.top().second == 1) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->left = new Node(arr[idx]);\n pair<Node*, int> lp = {st.top().first->left, 1};\n st.push(lp);\n }\n else {\n st.top().first->left = nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*, int> rp = {st.top().first->right, 1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n }\n return root;\n}\n\n\nvoid iterativePrePostInTraversal(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 = construct(arr);\n iterativePrePostInTraversal(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 iterativePrePostInTraversal(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 iterativePrePostInTraversal(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\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 \n \n \ndef iterativePrePostInTraversal(node):\n # write your code here\n \n \n\nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\n\nroot = construct(arr)\niterativePrePostInTraversal(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 25 12 37 30 75 62 70 87 \r\n12 25 30 37 50 62 70 75 87 \r\n12 30 37 25 70 62 87 75 50","questionVideo":"https://www.youtube.com/embed/d97z0fGBjpE","hints":[],"associated":[{"id":"204408f3-6b6f-4d09-9a0d-7aacf3699e00","name":"What is In Order of this Binary Tree - 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n ?","slug":"what-is-in-order-of-this-binary-tree-50-25-12-n-n-37-30-n-n-n-75-62-n-70-n-n-87-n-n","type":4},{"id":"6a8dc66e-d234-4f1e-a998-512456b40c23","name":"What is the Time Complexity of \"Iterative Pre, post and Inorder\"?","slug":"what-is-the-time-complexity-of-iterative-pre-post-and-inorder","type":4},{"id":"70b2ce6b-5f5b-4239-9328-ca7f0816b653","name":"What is Pre Order of this Binary Tree - 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n ?","slug":"what-is-pre-order-of-this-binary-tree-50-25-12-n-n-37-30-n-n-n-75-62-n-70-n-n-87-n-n","type":4},{"id":"ebbb7535-9a85-49c0-a15f-64e0dfa42607","name":"What is Post Order of this Binary Tree - 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n ?","slug":"what-is-post-order-of-this-binary-tree-50-25-12-n-n-37-30-n-n-n-75-62-n-70-n-n-87-n-n","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":"706f5513-c79d-43f2-9ee2-625dc215b138","name":"Iterative Pre, Post And Inorder Traversals Of Binary Tree","slug":"iterative-pre-post-and-inorder-traversals-of-binary-tree","type":1}],"next":{"id":"95f01142-a60f-4a99-a388-e19d3d0c6a47","name":"Iterative Pre, Post And Inorder In Binary Tree","type":3,"slug":"iterative-pre-post-and-inorder-in-binary-tree"},"prev":{"id":"55fadc18-9c8c-41f1-9717-bbcdb4d991a0","name":"Level Order Traversal Of Binary Tree","type":3,"slug":"level-order-traversal-of-binary-tree"}}}
plane

Editor

Loading...

Iterative Pre, Post And Inorder Traversals Of Binary Tree

easy

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of iterativePrePostInTraversal function. The function is expected to print pre order, in order and post order of the tree in separate lines (first pre, then in and finally post order). All elements in an order must be separated by a space. 3. Input is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

pre order (elements separated by space) in order (elements separated by space) post order (elements 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 12 37 30 75 62 70 87 12 25 30 37 50 62 70 75 87 12 30 37 25 70 62 87 75 50

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode