{"id":"7311f0f2-4172-4f9a-84ca-d3fa74477a8c","name":"Path To Leaf From Root In Range","description":"1. You are given a partially written BinaryTree class.\r\n2. You are given a value lo and a value hi\r\n3. You are required to complete the body of pathToLeafFromRoot function. The function is expected to print all paths from root to leaves which have sum of nodes in range from lo to hi (both inclusive). The elements in path should be separated by spaces. Each path should be in a separate line.\r\n4. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"The elements in path should be separated by spaces. Each path should be in a separate line.","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\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 void pathToLeafFromRoot(Node *node, string path, int sum, int lo, int hi){\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 int lo;\n cin>>lo;\n int hi;\n cin>>hi;\n \n Node *root = constructTree(arr);\n pathToLeafFromRoot(root, \"\", 0, lo, hi);\n return 0;\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 void pathToLeafFromRoot(Node node, String path, int sum, int lo, int hi){\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 int lo = Integer.parseInt(br.readLine());\r\n int hi = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n pathToLeafFromRoot(root, \"\", 0, lo, hi);\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 \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 pathToLeafFromRoot( node , path , sum, lo , hi):\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 lo = int(input())\n hi = int(input())\n\n\n root = construct(arr)\n #display(root)\n pathToLeafFromRoot(root, \"\", 0, lo, hi)"}},"points":10,"difficulty":"easy","sampleInput":"23\r\n50 25 12 n n 37 30 n n 40 n n 75 62 60 n n 70 n n 87 n n\r\n150\r\n250","sampleOutput":"50 25 37 40\r\n50 75 62 60\r\n50 75 87","questionVideo":"https://www.youtube.com/embed/OMKPbSdYSPE","hints":[],"associated":[{"id":"11d9c952-1fe1-4761-add7-377f97507e64","name":"Which of the following is not an advantage of trees?","slug":"which-of-the-following-is-not-an-advantage-of-trees","type":4},{"id":"8c02dff0-cc46-48a2-a942-fca4618f07a0","name":"The number of edges from the root to the node is called __________ of the tree.","slug":"the-number-of-edges-from-the-root-to-the-node-is-called-of-the-tree","type":4},{"id":"8e93f904-9b96-4d09-a483-144bf4213daf","name":"In binary tree, there can be:","slug":"in-binary-tree-there-can-be","type":4},{"id":"c37ef59f-a1ff-48bf-8fc8-c5d5f9f1baca","name":"Which of the following is incorrect with respect to binary trees?","slug":"which-of-the-following-is-incorrect-with-respect-to-binary-trees","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":"2c464955-97f3-4610-abcf-a610ba1daa39","name":"Path To Leaf From Root In Range","slug":"path-to-leaf-from-root-in-range","type":1}],"next":{"id":"31a390f5-774e-4837-8e2d-c5ac99d34fd5","name":"Path to Leaf From Root in Range","type":3,"slug":"path-to-leaf-from-root-in-range"},"prev":{"id":"cef67655-4d98-422d-a4e6-1c574a5685ec","name":"Print Nodes K Distance Away","type":3,"slug":"print-nodes-k-distance-away"}}}

Path To Leaf From Root In Range

1. You are given a partially written BinaryTree class. 2. You are given a value lo and a value hi 3. You are required to complete the body of pathToLeafFromRoot function. The function is expected to print all paths from root to leaves which have sum of nodes in range from lo to hi (both inclusive). The elements in path should be separated by spaces. Each path should be in a separate line. 4. Input is managed for you.

{"id":"7311f0f2-4172-4f9a-84ca-d3fa74477a8c","name":"Path To Leaf From Root In Range","description":"1. You are given a partially written BinaryTree class.\r\n2. You are given a value lo and a value hi\r\n3. You are required to complete the body of pathToLeafFromRoot function. The function is expected to print all paths from root to leaves which have sum of nodes in range from lo to hi (both inclusive). The elements in path should be separated by spaces. Each path should be in a separate line.\r\n4. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"The elements in path should be separated by spaces. Each path should be in a separate line.","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\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 void pathToLeafFromRoot(Node *node, string path, int sum, int lo, int hi){\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 int lo;\n cin>>lo;\n int hi;\n cin>>hi;\n \n Node *root = constructTree(arr);\n pathToLeafFromRoot(root, \"\", 0, lo, hi);\n return 0;\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 void pathToLeafFromRoot(Node node, String path, int sum, int lo, int hi){\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 int lo = Integer.parseInt(br.readLine());\r\n int hi = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n pathToLeafFromRoot(root, \"\", 0, lo, hi);\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 \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 pathToLeafFromRoot( node , path , sum, lo , hi):\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 lo = int(input())\n hi = int(input())\n\n\n root = construct(arr)\n #display(root)\n pathToLeafFromRoot(root, \"\", 0, lo, hi)"}},"points":10,"difficulty":"easy","sampleInput":"23\r\n50 25 12 n n 37 30 n n 40 n n 75 62 60 n n 70 n n 87 n n\r\n150\r\n250","sampleOutput":"50 25 37 40\r\n50 75 62 60\r\n50 75 87","questionVideo":"https://www.youtube.com/embed/OMKPbSdYSPE","hints":[],"associated":[{"id":"11d9c952-1fe1-4761-add7-377f97507e64","name":"Which of the following is not an advantage of trees?","slug":"which-of-the-following-is-not-an-advantage-of-trees","type":4},{"id":"8c02dff0-cc46-48a2-a942-fca4618f07a0","name":"The number of edges from the root to the node is called __________ of the tree.","slug":"the-number-of-edges-from-the-root-to-the-node-is-called-of-the-tree","type":4},{"id":"8e93f904-9b96-4d09-a483-144bf4213daf","name":"In binary tree, there can be:","slug":"in-binary-tree-there-can-be","type":4},{"id":"c37ef59f-a1ff-48bf-8fc8-c5d5f9f1baca","name":"Which of the following is incorrect with respect to binary trees?","slug":"which-of-the-following-is-incorrect-with-respect-to-binary-trees","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":"2c464955-97f3-4610-abcf-a610ba1daa39","name":"Path To Leaf From Root In Range","slug":"path-to-leaf-from-root-in-range","type":1}],"next":{"id":"31a390f5-774e-4837-8e2d-c5ac99d34fd5","name":"Path to Leaf From Root in Range","type":3,"slug":"path-to-leaf-from-root-in-range"},"prev":{"id":"cef67655-4d98-422d-a4e6-1c574a5685ec","name":"Print Nodes K Distance Away","type":3,"slug":"print-nodes-k-distance-away"}}}
plane

Editor


Loading...

Path To Leaf From Root In Range

easy

1. You are given a partially written BinaryTree class. 2. You are given a value lo and a value hi 3. You are required to complete the body of pathToLeafFromRoot function. The function is expected to print all paths from root to leaves which have sum of nodes in range from lo to hi (both inclusive). The elements in path should be separated by spaces. Each path should be in a separate line. 4. Input is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

The elements in path should be separated by spaces. Each path should be in a separate line.

Example

Sample Input

23 50 25 12 n n 37 30 n n 40 n n 75 62 60 n n 70 n n 87 n n 150 250

Sample Output

50 25 37 40 50 75 62 60 50 75 87

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode