{"id":"c33d7fb6-ca4c-49c1-83a6-e0526a5bc9b4","name":"Remove Leaves In Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of removeLeaves function. The function is expected to remove all leaf nodes from the tree.\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 <iostream>\n#include <vector>\n#include <algorithm>\n#include <queue>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\n int idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvoid display(Node *node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \"\";\n str += node->left == nullptr ? \".\" : to_string(node->left->data) + \"\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right == nullptr ? \".\" : to_string(node->right->data) + \"\";\n cout<<str<<endl;\n\n display(node->left);\n display(node->right);\n}\n\n Node *removeLeaves(Node *node){\n // write your code here\n \n }\n\n int main()\n {\n vector<int> arr;\n int n;\n cin>>n;\n \n for(int i = 0; i<n; i++){\n string inp;\n cin>>inp;\n if(inp != \"n\"){\n arr.push_back(stoi(inp));\n }\n else{\n arr.push_back(-1);\n }\n }\n \n \n Node *root = constructTree(arr);\n root = removeLeaves(root);\n display(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 Node 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 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 root = removeLeaves(root);\r\n display(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 = left\n self.right = right\n\nidx = 0\n\ndef construct(arr):\n global idx\n if idx == len(arr) or arr[idx] == -1:\n idx = idx+1\n return None\n node = Node(arr[idx],None,None)\n idx = idx+1\n node.left = construct(arr)\n node.right = construct(arr)\n return node\n\ndef display(node):\n if node:\n s = \"\"\n s += \".\" if node.left == None else str(node.left.data)\n s += \" <- \" + str(node.data) + \" -> \"\n s += \".\" if node.right == None else str(node.right.data)\n print(s)\n display(node.left)\n display(node.right)\n\ndef removeLeaves(node):\n \n # write your code here\n \n \nif __name__ == '__main__':\n\n n = int(input())\n s = input()\n l = list(s.split(\" \"))\n arr = []\n for i in range(len(l)):\n if(l[i] == 'n'):\n arr.append(-1)\n \n elif(l[i] == 'n\\r'):\n arr.append(-1)\n \n else:\n arr.append(int(l[i]))\n\n root = construct(arr)\n root = removeLeaves(root)\n display(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":"25 <- 50 -> 75\r\n. <- 25 -> 37\r\n. <- 37 -> .\r\n62 <- 75 -> .\r\n. <- 62 -> .","questionVideo":"https://www.youtube.com/embed/CkooURhePkg","hints":[],"associated":[{"id":"3f904fb1-710a-4214-9b6b-4ee4590ba6cc","name":"What will we return after we've executed both our calls?","slug":"what-will-we-return-after-we-ve-executed-both-our-calls","type":4},{"id":"79be00b5-0678-4482-bc16-84078f6d1c20","name":"What will be the time complexity in \"Removes leaves in binary tree\"?","slug":"what-will-be-the-time-complexity-in-removes-leaves-in-binary-tree","type":4},{"id":"b1862fc7-300e-47d7-81ea-e78dc0e1ce39","name":"What will we return when the leaf node is found?","slug":"what-will-we-return-when-the-leaf-node-is-found","type":4},{"id":"c6161302-d60f-4a46-913b-e1879b3e0dee","name":"Which type of node do we have to remove?","slug":"which-type-of-node-do-we-have-to-remove","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":"ecc970cb-2732-4721-b552-16bf656bbab3","name":"Remove Leaves In Binary Tree","slug":"remove-leaves-in-binary-tree","type":1}],"next":{"id":"17a1ed44-1063-44ba-9867-0f6cd63a82a6","name":"Remove Leaves In Binary Tree","type":3,"slug":"remove-leaves-in-binary-tree"},"prev":{"id":"24fdc673-45d7-4d17-b4b8-8f3f4b6abe6b","name":"Print Single Child Nodes","type":3,"slug":"print-single-child-nodes"}}}1. You are given a partially written BinaryTree class. 2. You are required to complete the body of removeLeaves function. The function is expected to remove all leaf nodes from the tree. 3. Input and Output is managed for you.
{"id":"c33d7fb6-ca4c-49c1-83a6-e0526a5bc9b4","name":"Remove Leaves In Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of removeLeaves function. The function is expected to remove all leaf nodes from the tree.\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 <iostream>\n#include <vector>\n#include <algorithm>\n#include <queue>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\n int idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvoid display(Node *node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \"\";\n str += node->left == nullptr ? \".\" : to_string(node->left->data) + \"\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right == nullptr ? \".\" : to_string(node->right->data) + \"\";\n cout<<str<<endl;\n\n display(node->left);\n display(node->right);\n}\n\n Node *removeLeaves(Node *node){\n // write your code here\n \n }\n\n int main()\n {\n vector<int> arr;\n int n;\n cin>>n;\n \n for(int i = 0; i<n; i++){\n string inp;\n cin>>inp;\n if(inp != \"n\"){\n arr.push_back(stoi(inp));\n }\n else{\n arr.push_back(-1);\n }\n }\n \n \n Node *root = constructTree(arr);\n root = removeLeaves(root);\n display(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 Node 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 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 root = removeLeaves(root);\r\n display(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 = left\n self.right = right\n\nidx = 0\n\ndef construct(arr):\n global idx\n if idx == len(arr) or arr[idx] == -1:\n idx = idx+1\n return None\n node = Node(arr[idx],None,None)\n idx = idx+1\n node.left = construct(arr)\n node.right = construct(arr)\n return node\n\ndef display(node):\n if node:\n s = \"\"\n s += \".\" if node.left == None else str(node.left.data)\n s += \" <- \" + str(node.data) + \" -> \"\n s += \".\" if node.right == None else str(node.right.data)\n print(s)\n display(node.left)\n display(node.right)\n\ndef removeLeaves(node):\n \n # write your code here\n \n \nif __name__ == '__main__':\n\n n = int(input())\n s = input()\n l = list(s.split(\" \"))\n arr = []\n for i in range(len(l)):\n if(l[i] == 'n'):\n arr.append(-1)\n \n elif(l[i] == 'n\\r'):\n arr.append(-1)\n \n else:\n arr.append(int(l[i]))\n\n root = construct(arr)\n root = removeLeaves(root)\n display(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":"25 <- 50 -> 75\r\n. <- 25 -> 37\r\n. <- 37 -> .\r\n62 <- 75 -> .\r\n. <- 62 -> .","questionVideo":"https://www.youtube.com/embed/CkooURhePkg","hints":[],"associated":[{"id":"3f904fb1-710a-4214-9b6b-4ee4590ba6cc","name":"What will we return after we've executed both our calls?","slug":"what-will-we-return-after-we-ve-executed-both-our-calls","type":4},{"id":"79be00b5-0678-4482-bc16-84078f6d1c20","name":"What will be the time complexity in \"Removes leaves in binary tree\"?","slug":"what-will-be-the-time-complexity-in-removes-leaves-in-binary-tree","type":4},{"id":"b1862fc7-300e-47d7-81ea-e78dc0e1ce39","name":"What will we return when the leaf node is found?","slug":"what-will-we-return-when-the-leaf-node-is-found","type":4},{"id":"c6161302-d60f-4a46-913b-e1879b3e0dee","name":"Which type of node do we have to remove?","slug":"which-type-of-node-do-we-have-to-remove","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":"ecc970cb-2732-4721-b552-16bf656bbab3","name":"Remove Leaves In Binary Tree","slug":"remove-leaves-in-binary-tree","type":1}],"next":{"id":"17a1ed44-1063-44ba-9867-0f6cd63a82a6","name":"Remove Leaves In Binary Tree","type":3,"slug":"remove-leaves-in-binary-tree"},"prev":{"id":"24fdc673-45d7-4d17-b4b8-8f3f4b6abe6b","name":"Print Single Child Nodes","type":3,"slug":"print-single-child-nodes"}}}
Editor
Discussions
Show Discussion
Related Resources
