{"id":"7ceabd5f-1d3b-4b63-97c4-5cf3bb74f358","name":"Remove Leaves In Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of removeLeaves function. The function is expected to remove all leaves from the tree. For more details, check out the question video.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","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\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" -> \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\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}\n\nvoid removeLeaves(Node *node)\n{\n// write code here\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 \n removeLeaves(root);\n display(root);\n \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 Stack<Node> stack = new Stack<>();\r\n stack.add(node);\r\n\r\n Stack<Node> cstack = new Stack<>();\r\n int level = 0;\r\n\r\n while (stack.size() > 0) {\r\n node = stack.pop();\r\n System.out.print(node.data + \" \");\r\n\r\n if (level % 2 == 0) {\r\n for (int i = 0; i < node.children.size(); i++) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n } else {\r\n for (int i = node.children.size() - 1; i >= 0; i--) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n }\r\n\r\n if (stack.size() == 0) {\r\n stack = cstack;\r\n cstack = new Stack<>();\r\n level++;\r\n System.out.println();\r\n }\r\n }\r\n }\r\n\r\n public static void mirror(Node node) {\r\n for (Node child : node.children) {\r\n mirror(child);\r\n }\r\n Collections.reverse(node.children);\r\n }\r\n\r\n public static void removeLeaves(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 removeLeaves(root);\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \n def _init_(self, key, children):\n self.key = key\n self.children=[]\ndef newNode(key): \n temp = Node()\n temp.key = key;\n temp.children = []\n return temp\n \n \ndef display(root):\n s = \"\"\n s = str(root.key) + \" -> \"\n for child in root.children:\n s += str(child.key) + \", \"\n \n s += \".\" \n print(s)\n for child in root.children:\n display(child)\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].children.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef removeLeaves(root):\n # write code here\n \n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n)\nremoveLeaves(root)\ndisplay(root)"}},"points":10,"difficulty":"easy","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, 30, 40, .\r\n20 -> .\r\n30 -> 80, .\r\n80 -> .\r\n40 -> .","questionVideo":"https://www.youtube.com/embed/EqhPE8tJ-K8","hints":[],"associated":[{"id":"06e0c940-d83d-49b0-b0aa-43e378395ef9","name":"A leaf node is a node which has","slug":"a-leaf-node-is-a-node-which-has","type":4},{"id":"0cd854b0-4b40-4d17-86e4-5041bef15d91","name":"What is the time complexity of solving \"Remove Leaves in a generic tree\"?","slug":"what-is-the-time-complexity-of-solving-remove-leaves-in-a-generic-tree","type":4},{"id":"1d794e99-e272-48e9-a0e6-e1ddeb27d395","name":"What is the space complexity of solving \"Remove Leaves in a generic tree\"?","slug":"what-is-the-space-complexity-of-solving-remove-leaves-in-a-generic-tree","type":4},{"id":"6722cb21-652e-4f97-8798-4ee7022eade6","name":"In this question, loop will start from","slug":"in-this-question-loop-will-start-from","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":"1deb83bc-949e-4815-81f9-832ddb3d843d","name":"Remove Leaves In Generic Tree","slug":"remove-leaves-in-generic-tree","type":1}],"next":{"id":"6edf26fe-c378-4244-93f6-705d85bf5942","name":"Remove Leaves in Generic Tree","type":3,"slug":"remove-leaves-in-generic-tree"},"prev":{"id":"401af9aa-1923-402d-b676-df21965892b7","name":"Mirror Of A Generic Tree","type":3,"slug":"mirror-of-a-generic-tree"}}}

Remove Leaves In Generic Tree

1. You are given a partially written GenericTree class. 2. You are required to complete the body of removeLeaves function. The function is expected to remove all leaves from the tree. For more details, check out the question video. 3. Input and Output is managed for you.

{"id":"7ceabd5f-1d3b-4b63-97c4-5cf3bb74f358","name":"Remove Leaves In Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of removeLeaves function. The function is expected to remove all leaves from the tree. For more details, check out the question video.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","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\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" -> \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\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}\n\nvoid removeLeaves(Node *node)\n{\n// write code here\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 \n removeLeaves(root);\n display(root);\n \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 Stack<Node> stack = new Stack<>();\r\n stack.add(node);\r\n\r\n Stack<Node> cstack = new Stack<>();\r\n int level = 0;\r\n\r\n while (stack.size() > 0) {\r\n node = stack.pop();\r\n System.out.print(node.data + \" \");\r\n\r\n if (level % 2 == 0) {\r\n for (int i = 0; i < node.children.size(); i++) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n } else {\r\n for (int i = node.children.size() - 1; i >= 0; i--) {\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n }\r\n\r\n if (stack.size() == 0) {\r\n stack = cstack;\r\n cstack = new Stack<>();\r\n level++;\r\n System.out.println();\r\n }\r\n }\r\n }\r\n\r\n public static void mirror(Node node) {\r\n for (Node child : node.children) {\r\n mirror(child);\r\n }\r\n Collections.reverse(node.children);\r\n }\r\n\r\n public static void removeLeaves(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 removeLeaves(root);\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \n def _init_(self, key, children):\n self.key = key\n self.children=[]\ndef newNode(key): \n temp = Node()\n temp.key = key;\n temp.children = []\n return temp\n \n \ndef display(root):\n s = \"\"\n s = str(root.key) + \" -> \"\n for child in root.children:\n s += str(child.key) + \", \"\n \n s += \".\" \n print(s)\n for child in root.children:\n display(child)\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].children.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef removeLeaves(root):\n # write code here\n \n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n)\nremoveLeaves(root)\ndisplay(root)"}},"points":10,"difficulty":"easy","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, 30, 40, .\r\n20 -> .\r\n30 -> 80, .\r\n80 -> .\r\n40 -> .","questionVideo":"https://www.youtube.com/embed/EqhPE8tJ-K8","hints":[],"associated":[{"id":"06e0c940-d83d-49b0-b0aa-43e378395ef9","name":"A leaf node is a node which has","slug":"a-leaf-node-is-a-node-which-has","type":4},{"id":"0cd854b0-4b40-4d17-86e4-5041bef15d91","name":"What is the time complexity of solving \"Remove Leaves in a generic tree\"?","slug":"what-is-the-time-complexity-of-solving-remove-leaves-in-a-generic-tree","type":4},{"id":"1d794e99-e272-48e9-a0e6-e1ddeb27d395","name":"What is the space complexity of solving \"Remove Leaves in a generic tree\"?","slug":"what-is-the-space-complexity-of-solving-remove-leaves-in-a-generic-tree","type":4},{"id":"6722cb21-652e-4f97-8798-4ee7022eade6","name":"In this question, loop will start from","slug":"in-this-question-loop-will-start-from","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":"1deb83bc-949e-4815-81f9-832ddb3d843d","name":"Remove Leaves In Generic Tree","slug":"remove-leaves-in-generic-tree","type":1}],"next":{"id":"6edf26fe-c378-4244-93f6-705d85bf5942","name":"Remove Leaves in Generic Tree","type":3,"slug":"remove-leaves-in-generic-tree"},"prev":{"id":"401af9aa-1923-402d-b676-df21965892b7","name":"Mirror Of A Generic Tree","type":3,"slug":"mirror-of-a-generic-tree"}}}
plane

Editor


Loading...

Remove Leaves In Generic Tree

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of removeLeaves function. The function is expected to remove all leaves from the tree. For more details, check out the question video. 3. Input and Output is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

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, 30, 40, . 20 -> . 30 -> 80, . 80 -> . 40 -> .

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode