{"id":"4a5a050a-cc0d-474b-8f71-e157ba9b80ab","name":"Node To Root Path In Generic Tree","description":"<p>1. You are given a partially written GenericTree class. 2. You are required to complete the body of nodeToRootPath function. The function is expected to return in form of linked list the path from element to root, if the element with data is found. 3. Input and Output is managed for you.</p>","inputFormat":"<p>Input is managed for you</p>","outputFormat":"<p>Output is managed for you</p>","constraints":"<p>None</p>","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\r\n#include<climits>\r\n\r\nusing namespace std;\r\n\r\nclass Node\r\n{\r\npublic:\r\n int data = 0;\r\n vector<Node *> children;\r\n\r\n Node(int data)\r\n {\r\n this->data = data;\r\n }\r\n};\r\n\r\n\r\nvoid display(Node *node)\r\n{\r\n string s = \"\";\r\n s += to_string(node->data) + \" Child: \";\r\n for (Node *child : node->children)\r\n {\r\n s += to_string(child->data) + \", \";\r\n }\r\n\r\n cout << s << \".\" << endl;\r\n\r\n for (Node *child : node->children)\r\n {\r\n display(child);\r\n }\r\n}\r\n\r\n\r\nNode *constructor01(vector<int> &arr)\r\n{\r\n if (arr.size() == 0)\r\n return NULL;\r\n\r\n vector<Node *> stack;\r\n stack.push_back(new Node(arr[0]));\r\n\r\n Node *root = stack[0];\r\n\r\n for (int i = 1; i < arr.size(); i++)\r\n {\r\n if (arr[i] != -1)\r\n {\r\n Node *node = stack.back();\r\n Node *nnode = new Node(arr[i]);\r\n\r\n node->children.push_back(nnode);\r\n stack.push_back(nnode);\r\n }\r\n else\r\n stack.pop_back();\r\n }\r\n return root;\r\n}\r\n\r\nvector<int> nodeToRootPath(Node *node, int data)\r\n{\r\n\r\n // Write your code here\r\n}\r\n\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin>>n;\r\n vector<int>arr(n,0);\r\n for(int i = 0; i < arr.size(); i++)\r\n {\r\n cin>>arr[i];\r\n }\r\n \r\n int data;\r\n cin>>data;\r\n \r\n Node *root = constructor01(arr);\r\n vector<int> ans = nodeToRootPath(root,data);\r\n \r\n cout<<\"[\";\r\n for(int i =0 ; i < ans.size(); i++)\r\n {\r\n cout<<ans[i];\r\n if(i!=ans.size()-1)\r\n cout<<\", \";\r\n }\r\n cout<<\"]\";\r\n \r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\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 ArrayList<Integer> nodeToRootPath(Node node, int data){\r\n // write your code here\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 int data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n ArrayList<Integer> path = nodeToRootPath(root, data);\r\n System.out.println(path);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\r\n def __init__(self, data):\r\n self.data = data\r\n self.children = []\r\n\r\n# create a new tree node\r\n\r\ndef newNode(data):\r\n temp = Node(data)\r\n return temp \r\n\r\n\r\n# n-ary tree level wise\r\n\r\ndef constructor(lst, n):\r\n root = None\r\n stack = []\r\n for i in range(0, n) :\r\n if lst[i] == -1:\r\n stack.pop()\r\n else:\r\n t = Node(lst[i])\r\n if len(stack) > 0:\r\n stack[-1].children.append(t)\r\n\r\n else:\r\n root = t\r\n\r\n stack.append(t)\r\n\r\n return root\r\n\r\n\r\ndef nodeToRootPath(root,val):\r\n \r\n # Write your code here\r\n \r\n \r\n\r\n# main function\r\n\r\nif __name__ == \"__main__\":\r\n lst = [] \r\n n = int(input())\r\n lst = list(map(int, input().split(\" \")))\r\n val = int(input())\r\n root = constructor(lst, n)\r\n path = nodeToRootPath(root, val)\r\n print(path)"}},"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\r\n120","sampleOutput":"[120, 80, 30, 10]","questionVideo":"https://www.youtube.com/embed/5r6yB_muOj4","hints":[],"associated":[{"id":"0af2f209-fee8-4ffb-a138-cd679d8fbd3d","name":"In generic tree, there can be:","slug":"in-generic-tree-there-can-be","type":4},{"id":"6ee67ec4-6bcb-4284-907e-3907dfc7b167","name":"What will be the time-complexity for finding node_to_root_Path in generic tree?","slug":"what-will-be-the-time-complexity-for-finding-node-to-root-path-in-generic-tree","type":4},{"id":"7be74cba-23e9-41c7-ad63-e173715f21a4","name":"What will be the space-complexity for finding node_to_root_Path in generic tree?","slug":"what-will-be-the-space-complexity-for-finding-node-to-root-path-in-generic-tree","type":4},{"id":"7f2ecee6-b299-4c15-b309-a08f7e9ded56","name":"Which of these is incorrect about functions of stack?","slug":"which-of-these-is-incorrect-about-functions-of-stack","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":"914505a2-1b12-494e-8e03-dfad454369ca","name":"Node To Root Path In Generic Tree","slug":"node-to-root-path-in-generic-tree","type":1}],"next":{"id":"1513c0cf-08a6-4053-8539-befcbff18990","name":"Node To Root Path In Generic Tree","type":3,"slug":"node-to-root-path-in-generic-tree"},"prev":{"id":"396290de-f968-439b-bdee-eb3895a8576b","name":"Find in Generic Tree","type":3,"slug":"find-in-generic-tree"}}}

Node To Root Path In Generic Tree

<p>1. You are given a partially written GenericTree class. 2. You are required to complete the body of nodeToRootPath function. The function is expected to return in form of linked list the path from element to root, if the element with data is found. 3. Input and Output is managed for you.</p>

{"id":"4a5a050a-cc0d-474b-8f71-e157ba9b80ab","name":"Node To Root Path In Generic Tree","description":"<p>1. You are given a partially written GenericTree class. 2. You are required to complete the body of nodeToRootPath function. The function is expected to return in form of linked list the path from element to root, if the element with data is found. 3. Input and Output is managed for you.</p>","inputFormat":"<p>Input is managed for you</p>","outputFormat":"<p>Output is managed for you</p>","constraints":"<p>None</p>","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\r\n#include<climits>\r\n\r\nusing namespace std;\r\n\r\nclass Node\r\n{\r\npublic:\r\n int data = 0;\r\n vector<Node *> children;\r\n\r\n Node(int data)\r\n {\r\n this->data = data;\r\n }\r\n};\r\n\r\n\r\nvoid display(Node *node)\r\n{\r\n string s = \"\";\r\n s += to_string(node->data) + \" Child: \";\r\n for (Node *child : node->children)\r\n {\r\n s += to_string(child->data) + \", \";\r\n }\r\n\r\n cout << s << \".\" << endl;\r\n\r\n for (Node *child : node->children)\r\n {\r\n display(child);\r\n }\r\n}\r\n\r\n\r\nNode *constructor01(vector<int> &arr)\r\n{\r\n if (arr.size() == 0)\r\n return NULL;\r\n\r\n vector<Node *> stack;\r\n stack.push_back(new Node(arr[0]));\r\n\r\n Node *root = stack[0];\r\n\r\n for (int i = 1; i < arr.size(); i++)\r\n {\r\n if (arr[i] != -1)\r\n {\r\n Node *node = stack.back();\r\n Node *nnode = new Node(arr[i]);\r\n\r\n node->children.push_back(nnode);\r\n stack.push_back(nnode);\r\n }\r\n else\r\n stack.pop_back();\r\n }\r\n return root;\r\n}\r\n\r\nvector<int> nodeToRootPath(Node *node, int data)\r\n{\r\n\r\n // Write your code here\r\n}\r\n\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin>>n;\r\n vector<int>arr(n,0);\r\n for(int i = 0; i < arr.size(); i++)\r\n {\r\n cin>>arr[i];\r\n }\r\n \r\n int data;\r\n cin>>data;\r\n \r\n Node *root = constructor01(arr);\r\n vector<int> ans = nodeToRootPath(root,data);\r\n \r\n cout<<\"[\";\r\n for(int i =0 ; i < ans.size(); i++)\r\n {\r\n cout<<ans[i];\r\n if(i!=ans.size()-1)\r\n cout<<\", \";\r\n }\r\n cout<<\"]\";\r\n \r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\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 ArrayList<Integer> nodeToRootPath(Node node, int data){\r\n // write your code here\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 int data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n ArrayList<Integer> path = nodeToRootPath(root, data);\r\n System.out.println(path);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\r\n def __init__(self, data):\r\n self.data = data\r\n self.children = []\r\n\r\n# create a new tree node\r\n\r\ndef newNode(data):\r\n temp = Node(data)\r\n return temp \r\n\r\n\r\n# n-ary tree level wise\r\n\r\ndef constructor(lst, n):\r\n root = None\r\n stack = []\r\n for i in range(0, n) :\r\n if lst[i] == -1:\r\n stack.pop()\r\n else:\r\n t = Node(lst[i])\r\n if len(stack) > 0:\r\n stack[-1].children.append(t)\r\n\r\n else:\r\n root = t\r\n\r\n stack.append(t)\r\n\r\n return root\r\n\r\n\r\ndef nodeToRootPath(root,val):\r\n \r\n # Write your code here\r\n \r\n \r\n\r\n# main function\r\n\r\nif __name__ == \"__main__\":\r\n lst = [] \r\n n = int(input())\r\n lst = list(map(int, input().split(\" \")))\r\n val = int(input())\r\n root = constructor(lst, n)\r\n path = nodeToRootPath(root, val)\r\n print(path)"}},"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\r\n120","sampleOutput":"[120, 80, 30, 10]","questionVideo":"https://www.youtube.com/embed/5r6yB_muOj4","hints":[],"associated":[{"id":"0af2f209-fee8-4ffb-a138-cd679d8fbd3d","name":"In generic tree, there can be:","slug":"in-generic-tree-there-can-be","type":4},{"id":"6ee67ec4-6bcb-4284-907e-3907dfc7b167","name":"What will be the time-complexity for finding node_to_root_Path in generic tree?","slug":"what-will-be-the-time-complexity-for-finding-node-to-root-path-in-generic-tree","type":4},{"id":"7be74cba-23e9-41c7-ad63-e173715f21a4","name":"What will be the space-complexity for finding node_to_root_Path in generic tree?","slug":"what-will-be-the-space-complexity-for-finding-node-to-root-path-in-generic-tree","type":4},{"id":"7f2ecee6-b299-4c15-b309-a08f7e9ded56","name":"Which of these is incorrect about functions of stack?","slug":"which-of-these-is-incorrect-about-functions-of-stack","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":"914505a2-1b12-494e-8e03-dfad454369ca","name":"Node To Root Path In Generic Tree","slug":"node-to-root-path-in-generic-tree","type":1}],"next":{"id":"1513c0cf-08a6-4053-8539-befcbff18990","name":"Node To Root Path In Generic Tree","type":3,"slug":"node-to-root-path-in-generic-tree"},"prev":{"id":"396290de-f968-439b-bdee-eb3895a8576b","name":"Find in Generic Tree","type":3,"slug":"find-in-generic-tree"}}}
plane

Editor


Loading...

Node To Root Path In Generic Tree

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of nodeToRootPath function. The function is expected to return in form of linked list the path from element to root, if the element with data is found. 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 120

Sample Output

[120, 80, 30, 10]

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode