`{"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, 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,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 = *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, 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,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 = *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"}}}` Editor

# 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.

None

## Format

### Input

Input is managed for you

### Output

Output is managed for you

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}19 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n 30```

### Sample Output

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}true [30, 37, 25, 50]```

Question Video

Discussions

Show Discussion

Related Resources 