{"id":"273b28d6-a678-4335-a26d-27ef80f5aa62","name":"Generic Tree - Traversals (pre-order, Post-order)","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of traversals function. The function is expected to visit every node. While traversing the function must print following content in different situations.\r\n 2.1. When the control reaches the node for the first time -> \"Node Pre\" node.data.\r\n 2.2. Before the control leaves for a child node from a node -> \"Edge Pre\" \r\n node.data--child.data.\r\n 2.3. After the control comes back to a node from a child -> \"Edge Post\" node.data- \r\n -child.data.\r\n 2.4. When the control is about to leave node, after the children have been visited \r\n -> \"Node Post\" node.data.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"As suggested in Sample Output","constraints":"None","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\nstruct Node{\n int data;\n vector<Node*>children;\n};\n\nNode *newNode(int key){\n\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int n ){\n Node *root=NULL;\n stack<Node*>st;\n for(int i=0;i<n;i++){\n if(arr[i]==-1){\n st.pop();\n }else{\n Node *t=newNode(arr[i]);\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\nvoid traversals(Node *node)\n{\n //write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n Node *root=construct(arr,n);\n traversals(root);\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 // 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 traversals(root);\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n \n def __init__(self, key):\n \n self.key = key\n self.child = []\n \ndef newNode(key): \n temp = Node(key)\n return temp\n \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= Node(lst[i])\n if len(stack) > 0:\n stack[-1].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef traversal(root):\n #write your code here\n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n) \ntraversal(root)"}},"points":10,"difficulty":"easy","sampleInput":"12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1","sampleOutput":"Node Pre 10\r\nEdge Pre 10--20\r\nNode Pre 20\r\nNode Post 20\r\nEdge Post 10--20\r\nEdge Pre 10--30\r\nNode Pre 30\r\nEdge Pre 30--50\r\nNode Pre 50\r\nNode Post 50\r\nEdge Post 30--50\r\nEdge Pre 30--60\r\nNode Pre 60\r\nNode Post 60\r\nEdge Post 30--60\r\nNode Post 30\r\nEdge Post 10--30\r\nEdge Pre 10--40\r\nNode Pre 40\r\nNode Post 40\r\nEdge Post 10--40\r\nNode Post 10","questionVideo":"https://www.youtube.com/embed/kL6tIGhVW1k","hints":[],"associated":[{"id":"38b586c3-4426-4cff-b8fc-cb6c92adda2e","name":"in postorder","slug":"in-postorder","type":4},{"id":"482429bd-5756-4be9-850a-1f35d52fdaf1","name":"in preorder","slug":"in-preorder","type":4},{"id":"977ae26c-e42b-4b4d-abcf-041ea6039113","name":"when do we print node-pre and node-post ?","slug":"when-do-we-print-node-pre-and-node-post","type":4},{"id":"cbb5adc8-8bdc-4cb0-bfdc-dfad6a5e26d4","name":"when do we print edge-pre and edge-post?","slug":"when-do-we-print-edge-pre-and-edge-post","type":4},{"id":"d8d65716-1066-47cd-adac-d81486df4a11","name":"what is the space and time complexity for the problem \"GENERIC TREE PRE ORDER AND POSTORDER\".","slug":"what-is-the-space-and-time-complexity-for-the-problem-generic-tree-pre-order-and-postorder","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":"c601dce1-7f1f-423b-b77c-c0afa905cd0e","name":"Generic Tree - Traversals (pre-order, Post-order)","slug":"generic-tree-traversals-pre-order-post-order","type":1}],"next":{"id":"b2a624bc-33cd-4250-ae7d-91aeb7bf5eb1","name":"Traversals In Generic Tree","type":3,"slug":"traversals-in-generic-tree"},"prev":{"id":"0c9f3712-613c-4eb8-8912-5310fd56ec22","name":"Height of a Generic Tree","type":3,"slug":"height-of-a-generic-tree"}}}

Generic Tree - Traversals (pre-order, Post-order)

1. You are given a partially written GenericTree class. 2. You are required to complete the body of traversals function. The function is expected to visit every node. While traversing the function must print following content in different situations. 2.1. When the control reaches the node for the first time -> "Node Pre" node.data. 2.2. Before the control leaves for a child node from a node -> "Edge Pre" node.data--child.data. 2.3. After the control comes back to a node from a child -> "Edge Post" node.data- -child.data. 2.4. When the control is about to leave node, after the children have been visited -> "Node Post" node.data. 3. Input is managed for you.

{"id":"273b28d6-a678-4335-a26d-27ef80f5aa62","name":"Generic Tree - Traversals (pre-order, Post-order)","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of traversals function. The function is expected to visit every node. While traversing the function must print following content in different situations.\r\n 2.1. When the control reaches the node for the first time -> \"Node Pre\" node.data.\r\n 2.2. Before the control leaves for a child node from a node -> \"Edge Pre\" \r\n node.data--child.data.\r\n 2.3. After the control comes back to a node from a child -> \"Edge Post\" node.data- \r\n -child.data.\r\n 2.4. When the control is about to leave node, after the children have been visited \r\n -> \"Node Post\" node.data.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"As suggested in Sample Output","constraints":"None","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\nstruct Node{\n int data;\n vector<Node*>children;\n};\n\nNode *newNode(int key){\n\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int n ){\n Node *root=NULL;\n stack<Node*>st;\n for(int i=0;i<n;i++){\n if(arr[i]==-1){\n st.pop();\n }else{\n Node *t=newNode(arr[i]);\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\nvoid traversals(Node *node)\n{\n //write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n Node *root=construct(arr,n);\n traversals(root);\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 // 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 traversals(root);\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n \n def __init__(self, key):\n \n self.key = key\n self.child = []\n \ndef newNode(key): \n temp = Node(key)\n return temp\n \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= Node(lst[i])\n if len(stack) > 0:\n stack[-1].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef traversal(root):\n #write your code here\n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n) \ntraversal(root)"}},"points":10,"difficulty":"easy","sampleInput":"12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1","sampleOutput":"Node Pre 10\r\nEdge Pre 10--20\r\nNode Pre 20\r\nNode Post 20\r\nEdge Post 10--20\r\nEdge Pre 10--30\r\nNode Pre 30\r\nEdge Pre 30--50\r\nNode Pre 50\r\nNode Post 50\r\nEdge Post 30--50\r\nEdge Pre 30--60\r\nNode Pre 60\r\nNode Post 60\r\nEdge Post 30--60\r\nNode Post 30\r\nEdge Post 10--30\r\nEdge Pre 10--40\r\nNode Pre 40\r\nNode Post 40\r\nEdge Post 10--40\r\nNode Post 10","questionVideo":"https://www.youtube.com/embed/kL6tIGhVW1k","hints":[],"associated":[{"id":"38b586c3-4426-4cff-b8fc-cb6c92adda2e","name":"in postorder","slug":"in-postorder","type":4},{"id":"482429bd-5756-4be9-850a-1f35d52fdaf1","name":"in preorder","slug":"in-preorder","type":4},{"id":"977ae26c-e42b-4b4d-abcf-041ea6039113","name":"when do we print node-pre and node-post ?","slug":"when-do-we-print-node-pre-and-node-post","type":4},{"id":"cbb5adc8-8bdc-4cb0-bfdc-dfad6a5e26d4","name":"when do we print edge-pre and edge-post?","slug":"when-do-we-print-edge-pre-and-edge-post","type":4},{"id":"d8d65716-1066-47cd-adac-d81486df4a11","name":"what is the space and time complexity for the problem \"GENERIC TREE PRE ORDER AND POSTORDER\".","slug":"what-is-the-space-and-time-complexity-for-the-problem-generic-tree-pre-order-and-postorder","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":"c601dce1-7f1f-423b-b77c-c0afa905cd0e","name":"Generic Tree - Traversals (pre-order, Post-order)","slug":"generic-tree-traversals-pre-order-post-order","type":1}],"next":{"id":"b2a624bc-33cd-4250-ae7d-91aeb7bf5eb1","name":"Traversals In Generic Tree","type":3,"slug":"traversals-in-generic-tree"},"prev":{"id":"0c9f3712-613c-4eb8-8912-5310fd56ec22","name":"Height of a Generic Tree","type":3,"slug":"height-of-a-generic-tree"}}}
plane

Editor

Loading...

Generic Tree - Traversals (pre-order, Post-order)

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of traversals function. The function is expected to visit every node. While traversing the function must print following content in different situations. 2.1. When the control reaches the node for the first time -> "Node Pre" node.data. 2.2. Before the control leaves for a child node from a node -> "Edge Pre" node.data--child.data. 2.3. After the control comes back to a node from a child -> "Edge Post" node.data- -child.data. 2.4. When the control is about to leave node, after the children have been visited -> "Node Post" node.data. 3. Input is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

As suggested in Sample Output

Example

Sample Input

12 10 20 -1 30 50 -1 60 -1 -1 40 -1 -1

Sample Output

Node Pre 10 Edge Pre 10--20 Node Pre 20 Node Post 20 Edge Post 10--20 Edge Pre 10--30 Node Pre 30 Edge Pre 30--50 Node Pre 50 Node Post 50 Edge Post 30--50 Edge Pre 30--60 Node Pre 60 Node Post 60 Edge Post 30--60 Node Post 30 Edge Post 10--30 Edge Pre 10--40 Node Pre 40 Node Post 40 Edge Post 10--40 Node Post 10

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode