{"id":"5fdb2c6a-b824-4b64-8873-92a63f529881","name":"Levelorder Linewise Zig Zag","description":" 1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of levelorderLineWiseZZ function. The function is expected to visit every node in \"levelorder fashion\" but in a zig-zag manner i.e. 1st level should be visited from left to right, 2nd level should be visited from right to left and so on. 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. \r\n \r\n ","inputFormat":"Input is managed for you","outputFormat":"All nodes on the same level should be separated by a space.\r\n1st level should be visited left to right, 2nd from right to left and so on alternately.\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\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}\nvoid levelOderZigZag(Node *node)\n\n{\n\n //write code here\n\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 levelOderZigZag(root);\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 levelOrderLinewiseZZ(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 levelOrderLinewiseZZ(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \n def _init_(self, key, child):\n \n self.key = key\n self.child = []\n \n # Utility function to create a new tree node\ndef newNode(key): \n temp = Node()\n temp.key = key;\n temp.child = []\n return temp\n \n\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].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef Linewisezigzag(root):\n \n # write code here\n \n \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# print(lst)\nroot = constructor(lst,n) \n# print(root.child[0].child[0].key)\nLinewisezigzag(root)\n"}},"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 \r\n40 30 20 \r\n50 60 70 80 90 100 \r\n120 110","questionVideo":"https://www.youtube.com/embed/Yde0l3q-qJs","hints":[],"associated":[],"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":"50150665-980a-45f7-854f-76da585fd327","name":"Levelorder Linewise Zig Zag","slug":"levelorder-linewise-zig-zag","type":1}],"next":{"id":"a39df833-917e-41a5-b7e6-cb0c0635fad7","name":"Level order Linewise Zig Zag","type":3,"slug":"level-order-linewise-zig-zag"},"prev":{"id":"d10b9bcf-aea8-43fc-803c-d791081d4079","name":"Level Order-Line Wise","type":3,"slug":"level-order-line-wise"}}}

Levelorder Linewise Zig Zag

1. You are given a partially written GenericTree class. 2. You are required to complete the body of levelorderLineWiseZZ function. The function is expected to visit every node in "levelorder fashion" but in a zig-zag manner i.e. 1st level should be visited from left to right, 2nd level should be visited from right to left and so on. 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":"5fdb2c6a-b824-4b64-8873-92a63f529881","name":"Levelorder Linewise Zig Zag","description":" 1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of levelorderLineWiseZZ function. The function is expected to visit every node in \"levelorder fashion\" but in a zig-zag manner i.e. 1st level should be visited from left to right, 2nd level should be visited from right to left and so on. 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. \r\n \r\n ","inputFormat":"Input is managed for you","outputFormat":"All nodes on the same level should be separated by a space.\r\n1st level should be visited left to right, 2nd from right to left and so on alternately.\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\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}\nvoid levelOderZigZag(Node *node)\n\n{\n\n //write code here\n\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 levelOderZigZag(root);\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 levelOrderLinewiseZZ(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 levelOrderLinewiseZZ(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \n def _init_(self, key, child):\n \n self.key = key\n self.child = []\n \n # Utility function to create a new tree node\ndef newNode(key): \n temp = Node()\n temp.key = key;\n temp.child = []\n return temp\n \n\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].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef Linewisezigzag(root):\n \n # write code here\n \n \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# print(lst)\nroot = constructor(lst,n) \n# print(root.child[0].child[0].key)\nLinewisezigzag(root)\n"}},"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 \r\n40 30 20 \r\n50 60 70 80 90 100 \r\n120 110","questionVideo":"https://www.youtube.com/embed/Yde0l3q-qJs","hints":[],"associated":[],"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":"50150665-980a-45f7-854f-76da585fd327","name":"Levelorder Linewise Zig Zag","slug":"levelorder-linewise-zig-zag","type":1}],"next":{"id":"a39df833-917e-41a5-b7e6-cb0c0635fad7","name":"Level order Linewise Zig Zag","type":3,"slug":"level-order-linewise-zig-zag"},"prev":{"id":"d10b9bcf-aea8-43fc-803c-d791081d4079","name":"Level Order-Line Wise","type":3,"slug":"level-order-line-wise"}}}
plane

Editor

Loading...

Levelorder Linewise Zig Zag

medium

1. You are given a partially written GenericTree class. 2. You are required to complete the body of levelorderLineWiseZZ function. The function is expected to visit every node in "levelorder fashion" but in a zig-zag manner i.e. 1st level should be visited from left to right, 2nd level should be visited from right to left and so on. 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 on the same level should be separated by a space. 1st level should be visited left to right, 2nd from right to left and so on alternately. 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 40 30 20 50 60 70 80 90 100 120 110

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode