{"id":"0cbe1e95-0d01-4224-ba9d-8d494a1a524c","name":"Find And Nodetorootpath In Binary Tree","description":"<p>1. You are given a partially written BinaryTree class. 2. You are given an element. 3. You are required to complete the body of find and nodeToRoot function. The functions are expected to 3.1. find -&gt; return true or false depending on if the data is found in binary tree. 3.2. nodeToRoot -&gt; returns the path from node (correspoding to data) to root in form of an arraylist (root being the last element) 4. Input iand Output is managed for you.</p>","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <string.h>\n#include <vector>\n\nusing namespace std;\n\nclass Node{\npublic:\n int data;\n Node* left = nullptr;\n Node* right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\nclass Pair{\npublic:\n Node* node = nullptr;\n int state = 0;\n\n Pair(Node* node, int state)\n {\n this->node = node;\n this->state = state;\n }\n};\n\nint idx = 0;\nNode* constructTree(vector<int>& arr){\n\n if (idx == arr.size() || arr[idx] == -1){\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 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}\nbool find(Node* node, int data){\n // write your code here\n}\n\nvector<int> nodeToRootPath(Node* node, int data){\n // write your code here\n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for (int i = 0; i < n; i++){\n string temp;\n cin >> temp;\n if (temp == \"n\"){\n arr[i] = -1;\n }else{\n arr[i] = stoi(temp);\n }\n }\n\n Node* root = constructTree(arr);\n int data;\n cin >> data;\n bool found = find(root, data);\n found == 1 ? cout << \"true\" << endl : cout << \"false\" << endl;\n vector<int> path = nodeToRootPath(root, data);\n cout << \"[\";\n for (int i = 0; i < path.size(); i++) {\n cout << path[i];\n if (i != path.size() - 1) {\n cout << \", \";\n }\n }\n cout << \"]\" << endl;\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 boolean find(Node node, int data){\r\n // write your code here\r\n }\r\n\r\n public static ArrayList<Integer> nodeToRootPath(Node node, int data){\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 data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n boolean found = find(root, data);\r\n System.out.println(found);\r\n\r\n ArrayList<Integer> path = nodeToRootPath(root, data);\r\n System.out.println(path);\r\n }\r\n\r\n}"},"python":{"code":"import queue\nclass Node:\n \n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n \n\ndef find(node,data):\n # write your code here \n \ndef nodeToRootPath(node, data):\n # write your code here \n \n \nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\ndata = int(input())\nans = []\nroot = construct(arr)\nfound = find(root,data)\nans = nodeToRootPath(root, data)\nif(found == True):\n print(\"true\")\nelse:\n print(\"false\")\nprint(ans)"}},"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\r\n30","sampleOutput":"true\r\n[30, 37, 25, 50]","questionVideo":"https://www.youtube.com/embed/p_8c3QYbDJ8","hints":[],"associated":[{"id":"48f0df33-dedf-4caf-bc68-1547e4ad2e48","name":"What do we mean by Node To Root Path?","slug":"what-do-we-mean-by-node-to-root-path","type":4},{"id":"c98b5fd0-bf25-4eee-a17e-caa79aa53b9d","name":"What will be the Time Complexity of \"Find and nodetorootpath in Binary tree\"?","slug":"what-will-be-the-time-complexity-of-find-and-nodetorootpath-in-binary-tree","type":4},{"id":"d94cb2da-8f5c-45bd-a318-8c1cdbf67c92","name":"What is the Space Complexity of \"Find and nodetorootpath in Binary tree\"?","slug":"what-is-the-space-complexity-of-find-and-nodetorootpath-in-binary-tree","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":"d260bf30-12ef-4654-a73d-3a98726cb19f","name":"Find And Nodetorootpath In Binary Tree","slug":"find-and-nodetorootpath-in-binary-tree","type":1}],"next":{"id":"463aae3a-7085-424d-842e-93e939058dd1","name":"Find Node to Root Path in Binary Tree","type":3,"slug":"find-node-to-root-path-in-binary-tree"},"prev":{"id":"95f01142-a60f-4a99-a388-e19d3d0c6a47","name":"Iterative Pre, Post And Inorder In Binary Tree","type":3,"slug":"iterative-pre-post-and-inorder-in-binary-tree"}}}

Find And Nodetorootpath In Binary Tree

<p>1. You are given a partially written BinaryTree class. 2. You are given an element. 3. You are required to complete the body of find and nodeToRoot function. The functions are expected to 3.1. find -&gt; return true or false depending on if the data is found in binary tree. 3.2. nodeToRoot -&gt; returns the path from node (correspoding to data) to root in form of an arraylist (root being the last element) 4. Input iand Output is managed for you.</p>

{"id":"0cbe1e95-0d01-4224-ba9d-8d494a1a524c","name":"Find And Nodetorootpath In Binary Tree","description":"<p>1. You are given a partially written BinaryTree class. 2. You are given an element. 3. You are required to complete the body of find and nodeToRoot function. The functions are expected to 3.1. find -&gt; return true or false depending on if the data is found in binary tree. 3.2. nodeToRoot -&gt; returns the path from node (correspoding to data) to root in form of an arraylist (root being the last element) 4. Input iand Output is managed for you.</p>","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <string.h>\n#include <vector>\n\nusing namespace std;\n\nclass Node{\npublic:\n int data;\n Node* left = nullptr;\n Node* right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\nclass Pair{\npublic:\n Node* node = nullptr;\n int state = 0;\n\n Pair(Node* node, int state)\n {\n this->node = node;\n this->state = state;\n }\n};\n\nint idx = 0;\nNode* constructTree(vector<int>& arr){\n\n if (idx == arr.size() || arr[idx] == -1){\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 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}\nbool find(Node* node, int data){\n // write your code here\n}\n\nvector<int> nodeToRootPath(Node* node, int data){\n // write your code here\n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for (int i = 0; i < n; i++){\n string temp;\n cin >> temp;\n if (temp == \"n\"){\n arr[i] = -1;\n }else{\n arr[i] = stoi(temp);\n }\n }\n\n Node* root = constructTree(arr);\n int data;\n cin >> data;\n bool found = find(root, data);\n found == 1 ? cout << \"true\" << endl : cout << \"false\" << endl;\n vector<int> path = nodeToRootPath(root, data);\n cout << \"[\";\n for (int i = 0; i < path.size(); i++) {\n cout << path[i];\n if (i != path.size() - 1) {\n cout << \", \";\n }\n }\n cout << \"]\" << endl;\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 boolean find(Node node, int data){\r\n // write your code here\r\n }\r\n\r\n public static ArrayList<Integer> nodeToRootPath(Node node, int data){\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 data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n boolean found = find(root, data);\r\n System.out.println(found);\r\n\r\n ArrayList<Integer> path = nodeToRootPath(root, data);\r\n System.out.println(path);\r\n }\r\n\r\n}"},"python":{"code":"import queue\nclass Node:\n \n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n \n\ndef find(node,data):\n # write your code here \n \ndef nodeToRootPath(node, data):\n # write your code here \n \n \nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\ndata = int(input())\nans = []\nroot = construct(arr)\nfound = find(root,data)\nans = nodeToRootPath(root, data)\nif(found == True):\n print(\"true\")\nelse:\n print(\"false\")\nprint(ans)"}},"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\r\n30","sampleOutput":"true\r\n[30, 37, 25, 50]","questionVideo":"https://www.youtube.com/embed/p_8c3QYbDJ8","hints":[],"associated":[{"id":"48f0df33-dedf-4caf-bc68-1547e4ad2e48","name":"What do we mean by Node To Root Path?","slug":"what-do-we-mean-by-node-to-root-path","type":4},{"id":"c98b5fd0-bf25-4eee-a17e-caa79aa53b9d","name":"What will be the Time Complexity of \"Find and nodetorootpath in Binary tree\"?","slug":"what-will-be-the-time-complexity-of-find-and-nodetorootpath-in-binary-tree","type":4},{"id":"d94cb2da-8f5c-45bd-a318-8c1cdbf67c92","name":"What is the Space Complexity of \"Find and nodetorootpath in Binary tree\"?","slug":"what-is-the-space-complexity-of-find-and-nodetorootpath-in-binary-tree","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":"d260bf30-12ef-4654-a73d-3a98726cb19f","name":"Find And Nodetorootpath In Binary Tree","slug":"find-and-nodetorootpath-in-binary-tree","type":1}],"next":{"id":"463aae3a-7085-424d-842e-93e939058dd1","name":"Find Node to Root Path in Binary Tree","type":3,"slug":"find-node-to-root-path-in-binary-tree"},"prev":{"id":"95f01142-a60f-4a99-a388-e19d3d0c6a47","name":"Iterative Pre, Post And Inorder In Binary Tree","type":3,"slug":"iterative-pre-post-and-inorder-in-binary-tree"}}}
plane

Editor

Loading...

Find And Nodetorootpath In Binary Tree

easy

1. You are given a partially written BinaryTree class. 2. You are given an element. 3. You are required to complete the body of find and nodeToRoot function. The functions are expected to 3.1. find -> return true or false depending on if the data is found in binary tree. 3.2. nodeToRoot -> returns the path from node (correspoding to data) to root in form of an arraylist (root being the last element) 4. Input iand Output is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

19 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n 30

Sample Output

true [30, 37, 25, 50]

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode