{"id":"a2f8de28-6867-492f-ae1b-b98f5b94ffa3","name":"Iterative Preorder And Postorder Of Generic Tree","description":"<p>1. You are given a partially written GenericTree class. 2. You are require to complete the body of function IterativePreandPostOrder. The function does not use recursion and prints preorder and postorder of the tree. Both orders are printed in separate lines (preorder first, followed by post order in next line). Elements in an order are separated by space. 3. Input and Output is managed for you.</p>","inputFormat":"Input is managed for you","outputFormat":"Elements in preorder separated by a space\r\nElements in postorder separated by a space","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nclass Node {\n public:\n int data;\n vector<Node*>children;\n};\n\nvoid iterativePreAndPostOrder(Node* root){\n\t//write your code here\n}\n\nNode* construct(vector<int>&arr) {\n Node* root = nullptr;\n\n stack <Node*> st;\n for (int i = 0; i < arr.size(); i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node* t = new Node();\n t->data = arr[i];\n\n if (st.size() > 0) {\n st.top()->children.push_back(t);\n } else {\n root = t;\n }\n st.push(t);\n }\n }\n return root;\n }\n \nint main(){\n int n,x;\n cin>>n;\n vector<int>arr;\n for(int i=0;i<n;i++){\n cin>>x;\n arr.push_back(x);\n }\n Node *root = construct(arr);\n iterativePreAndPostOrder(root);\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n private static class Node {\n int data;\n ArrayList<Node> children = new ArrayList<>();\n }\n\n public static void display(Node node) {\n String str = node.data + \" -> \";\n for (Node child : node.children) {\n str += child.data + \", \";\n }\n str += \".\";\n System.out.println(str);\n\n for (Node child : node.children) {\n display(child);\n }\n }\n\n public static Node construct(int[] arr) {\n Node root = null;\n\n Stack<Node> st = new Stack<>();\n for (int i = 0; i < arr.length; i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node t = new Node();\n t.data = arr[i];\n\n if (st.size() > 0) {\n st.peek().children.add(t);\n } else {\n root = t;\n }\n\n st.push(t);\n }\n }\n\n return root;\n }\n\n public static void IterativePreandPostOrder(Node node) {\n // write your code here\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int n = Integer.parseInt(br.readLine());\n int[] arr = new int[n];\n String[] values = br.readLine().split(\" \");\n for (int i = 0; i < n; i++) {\n arr[i] = Integer.parseInt(values[i]);\n }\n\n Node root = construct(arr);\n IterativePreandPostOrder(root);\n }\n\n}"},"python":{"code":"class Node:\n def __init__(self, key):\n self.data=key\n self.child=[]\n \ndef newNode(key):\n temp= Node(key)\n return temp\n \nclass Pair:\n def __init__(self,node,st):\n self.node=node;\n self.state=st\n\ndef construct(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=Node(lst[i])\n if len(stack)>0:\n stack[-1].child.append(t)\n else:\n root=t\n stack.append(t)\n return root\n \n\ndef IterativePreandPostOrder(node):\n #write your code here\n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nroot=construct(arr,n)\nIterativePreandPostOrder(root)"}},"points":10,"difficulty":"medium","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 -50 60 30 70 -80 110 -120 90 40 -100 \r\n-50 60 20 70 110 -120 -80 90 30 -100 40 10","questionVideo":"https://www.youtube.com/embed/CiOS8EczYB4","hints":[],"associated":[{"id":"270bde7a-f0de-4ec3-8a89-72fe014da45f","name":"Which data structure is best suited for this problem ?","slug":"which-data-structure-is-best-suited-for-this-problem","type":4},{"id":"3627ef68-1ecd-4ad6-9627-3fafe483f11e","name":"Why you can't use queue in this problem ?","slug":"why-you-can-t-use-queue-in-this-problem","type":4},{"id":"52f73763-4f97-4318-947e-bbfce9b891e0","name":"what is the difference between generic tree and binary tree ?","slug":"what-is-the-difference-between-generic-tree-and-binary-tree","type":4},{"id":"e80ebf8c-653e-40bf-bdfb-0f6d02dc0ad2","name":"Which algorithm can be implemented using single stack ?","slug":"which-algorithm-can-be-implemented-using-single-stack","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":"b7cec68b-90ae-4ca5-ab02-d8263bf3235c","name":"Iterative Preorder And Postorder Of Generic Tree","slug":"iterative-preorder-and-postorder-of-generic-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":"6ef720df-f5c2-47a4-9720-d623dbdcb6c4","name":"Diameter in a Generic Tree","type":3,"slug":"diameter-in-a-generic-tree"}}}

Iterative Preorder And Postorder Of Generic Tree

<p>1. You are given a partially written GenericTree class. 2. You are require to complete the body of function IterativePreandPostOrder. The function does not use recursion and prints preorder and postorder of the tree. Both orders are printed in separate lines (preorder first, followed by post order in next line). Elements in an order are separated by space. 3. Input and Output is managed for you.</p>

{"id":"a2f8de28-6867-492f-ae1b-b98f5b94ffa3","name":"Iterative Preorder And Postorder Of Generic Tree","description":"<p>1. You are given a partially written GenericTree class. 2. You are require to complete the body of function IterativePreandPostOrder. The function does not use recursion and prints preorder and postorder of the tree. Both orders are printed in separate lines (preorder first, followed by post order in next line). Elements in an order are separated by space. 3. Input and Output is managed for you.</p>","inputFormat":"Input is managed for you","outputFormat":"Elements in preorder separated by a space\r\nElements in postorder separated by a space","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nclass Node {\n public:\n int data;\n vector<Node*>children;\n};\n\nvoid iterativePreAndPostOrder(Node* root){\n\t//write your code here\n}\n\nNode* construct(vector<int>&arr) {\n Node* root = nullptr;\n\n stack <Node*> st;\n for (int i = 0; i < arr.size(); i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node* t = new Node();\n t->data = arr[i];\n\n if (st.size() > 0) {\n st.top()->children.push_back(t);\n } else {\n root = t;\n }\n st.push(t);\n }\n }\n return root;\n }\n \nint main(){\n int n,x;\n cin>>n;\n vector<int>arr;\n for(int i=0;i<n;i++){\n cin>>x;\n arr.push_back(x);\n }\n Node *root = construct(arr);\n iterativePreAndPostOrder(root);\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n private static class Node {\n int data;\n ArrayList<Node> children = new ArrayList<>();\n }\n\n public static void display(Node node) {\n String str = node.data + \" -> \";\n for (Node child : node.children) {\n str += child.data + \", \";\n }\n str += \".\";\n System.out.println(str);\n\n for (Node child : node.children) {\n display(child);\n }\n }\n\n public static Node construct(int[] arr) {\n Node root = null;\n\n Stack<Node> st = new Stack<>();\n for (int i = 0; i < arr.length; i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node t = new Node();\n t.data = arr[i];\n\n if (st.size() > 0) {\n st.peek().children.add(t);\n } else {\n root = t;\n }\n\n st.push(t);\n }\n }\n\n return root;\n }\n\n public static void IterativePreandPostOrder(Node node) {\n // write your code here\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int n = Integer.parseInt(br.readLine());\n int[] arr = new int[n];\n String[] values = br.readLine().split(\" \");\n for (int i = 0; i < n; i++) {\n arr[i] = Integer.parseInt(values[i]);\n }\n\n Node root = construct(arr);\n IterativePreandPostOrder(root);\n }\n\n}"},"python":{"code":"class Node:\n def __init__(self, key):\n self.data=key\n self.child=[]\n \ndef newNode(key):\n temp= Node(key)\n return temp\n \nclass Pair:\n def __init__(self,node,st):\n self.node=node;\n self.state=st\n\ndef construct(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=Node(lst[i])\n if len(stack)>0:\n stack[-1].child.append(t)\n else:\n root=t\n stack.append(t)\n return root\n \n\ndef IterativePreandPostOrder(node):\n #write your code here\n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nroot=construct(arr,n)\nIterativePreandPostOrder(root)"}},"points":10,"difficulty":"medium","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 -50 60 30 70 -80 110 -120 90 40 -100 \r\n-50 60 20 70 110 -120 -80 90 30 -100 40 10","questionVideo":"https://www.youtube.com/embed/CiOS8EczYB4","hints":[],"associated":[{"id":"270bde7a-f0de-4ec3-8a89-72fe014da45f","name":"Which data structure is best suited for this problem ?","slug":"which-data-structure-is-best-suited-for-this-problem","type":4},{"id":"3627ef68-1ecd-4ad6-9627-3fafe483f11e","name":"Why you can't use queue in this problem ?","slug":"why-you-can-t-use-queue-in-this-problem","type":4},{"id":"52f73763-4f97-4318-947e-bbfce9b891e0","name":"what is the difference between generic tree and binary tree ?","slug":"what-is-the-difference-between-generic-tree-and-binary-tree","type":4},{"id":"e80ebf8c-653e-40bf-bdfb-0f6d02dc0ad2","name":"Which algorithm can be implemented using single stack ?","slug":"which-algorithm-can-be-implemented-using-single-stack","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":"b7cec68b-90ae-4ca5-ab02-d8263bf3235c","name":"Iterative Preorder And Postorder Of Generic Tree","slug":"iterative-preorder-and-postorder-of-generic-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":"6ef720df-f5c2-47a4-9720-d623dbdcb6c4","name":"Diameter in a Generic Tree","type":3,"slug":"diameter-in-a-generic-tree"}}}
plane

Editor

Loading...

Iterative Preorder And Postorder Of Generic Tree

medium

1. You are given a partially written GenericTree class. 2. You are require to complete the body of function IterativePreandPostOrder. The function does not use recursion and prints preorder and postorder of the tree. Both orders are printed in separate lines (preorder first, followed by post order in next line). Elements in an order are separated by space. 3. Input and Output is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Elements in preorder separated by a space Elements in postorder separated by a space

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

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode