{"id":"6e3349d8-f21b-4844-b272-64f887967d42","name":"Lowest Common Ancestor (generic Tree)","description":"<p>1. You are given a partially written GenericTree class. 2. You are required to complete the body of lca function. The function is expected to return the lowest common ancestor of two data values that are passed to it. Please watch the question video to understand what lca is. 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> *rootNodeToPath(Node *node, int data)\r\n{\r\n\r\n if (node->data == data)\r\n {\r\n vector<int> *base = new vector<int>();\r\n base->push_back(data);\r\n return base;\r\n }\r\n\r\n vector<int> *ans = new vector<int>();\r\n for (Node *child : node->children)\r\n {\r\n vector<int> *recAns = rootNodeToPath(child, data);\r\n if (recAns->size() > 0)\r\n {\r\n recAns->push_back(node->data);\r\n return recAns;\r\n }\r\n }\r\n return ans;\r\n}\r\n\r\n\r\n\r\nint lca(Node *node, int data1, int data2)\r\n{\r\n \r\n // Write your code here\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 data1;\r\n cin>>data1;\r\n int data2;\r\n cin>>data2;\r\n \r\n Node *root = constructor01(arr);\r\n int Lca = lca(root,data1,data2);\r\n cout<<Lca<<endl;\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 if (node.data == data) {\r\n ArrayList<Integer> path = new ArrayList<>();\r\n path.add(node.data);\r\n return path;\r\n }\r\n\r\n for (Node child : node.children) {\r\n ArrayList<Integer> ptc = nodeToRootPath(child, data);\r\n if (ptc.size() > 0) {\r\n ptc.add(node.data);\r\n return ptc;\r\n }\r\n }\r\n\r\n return new ArrayList<>();\r\n }\r\n\r\n public static int lca(Node node, int d1, int d2) {\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 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 d1 = Integer.parseInt(br.readLine());\r\n int d2 = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n int lca = lca(root, d1, d2);\r\n System.out.println(lca);\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 if root.data == val:\r\n \r\n base_ans = []\r\n base_ans.append(root.data)\r\n return base_ans\r\n\r\n \r\n for child in root.children:\r\n pt = nodeToRootPath(child,val)\r\n \r\n if len(pt) > 0:\r\n pt.append(root.data)\r\n return pt\r\n \r\n way = []\r\n return way\r\n\r\ndef lca(root, data1, data2):\r\n \r\n # Write your code here\r\n \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 \r\n data1 = int(input())\r\n data2 = int(input())\r\n \r\n root = constructor(lst, n)\r\n ans = lca(root, data1, data2)\r\n print(ans)"}},"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\r\n80","sampleOutput":"80","questionVideo":"https://www.youtube.com/embed/5xlRdBskWJE","hints":[],"associated":[{"id":"07507a66-eb76-4348-8c5f-f47c21f65a24","name":"Is the function nodeToRootPath helpful for this question ?","slug":"is-the-function-nodetorootpath-helpful-for-this-question","type":4},{"id":"737994bf-b97b-4695-8916-f4487d943745","name":"What is the space complexity of \"Lowest common ancestor-Generic tree\"?","slug":"what-is-the-space-complexity-of-lowest-common-ancestor-generic-tree","type":4},{"id":"a467d46e-3d47-4573-ab78-3b9628cc856d","name":"What is the time complexity of \"Lowest common ancestor-Generic tree\"?","slug":"what-is-the-time-complexity-of-lowest-common-ancestor-generic-tree","type":4},{"id":"bb763ec3-1548-49f8-b875-0582ccf0bbce","name":"Two pointers are initialized at which place ?","slug":"two-pointers-are-initialized-at-which-place","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":"9f32a8b3-b329-4ae4-b666-1ef8f644bd13","name":"Lowest Common Ancestor (generic Tree)","slug":"lowest-common-ancestor-generic-tree","type":1}],"next":{"id":"e54f1209-5cb9-47aa-9892-9f9161819a8e","name":"Lowest Common Ancestor - Generic Tree","type":3,"slug":"lowest-common-ancestor-generic-tree"},"prev":{"id":"1513c0cf-08a6-4053-8539-befcbff18990","name":"Node To Root Path In Generic Tree","type":3,"slug":"node-to-root-path-in-generic-tree"}}}

Lowest Common Ancestor (generic Tree)

<p>1. You are given a partially written GenericTree class. 2. You are required to complete the body of lca function. The function is expected to return the lowest common ancestor of two data values that are passed to it. Please watch the question video to understand what lca is. 3. Input and Output is managed for you.</p>

{"id":"6e3349d8-f21b-4844-b272-64f887967d42","name":"Lowest Common Ancestor (generic Tree)","description":"<p>1. You are given a partially written GenericTree class. 2. You are required to complete the body of lca function. The function is expected to return the lowest common ancestor of two data values that are passed to it. Please watch the question video to understand what lca is. 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> *rootNodeToPath(Node *node, int data)\r\n{\r\n\r\n if (node->data == data)\r\n {\r\n vector<int> *base = new vector<int>();\r\n base->push_back(data);\r\n return base;\r\n }\r\n\r\n vector<int> *ans = new vector<int>();\r\n for (Node *child : node->children)\r\n {\r\n vector<int> *recAns = rootNodeToPath(child, data);\r\n if (recAns->size() > 0)\r\n {\r\n recAns->push_back(node->data);\r\n return recAns;\r\n }\r\n }\r\n return ans;\r\n}\r\n\r\n\r\n\r\nint lca(Node *node, int data1, int data2)\r\n{\r\n \r\n // Write your code here\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 data1;\r\n cin>>data1;\r\n int data2;\r\n cin>>data2;\r\n \r\n Node *root = constructor01(arr);\r\n int Lca = lca(root,data1,data2);\r\n cout<<Lca<<endl;\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 if (node.data == data) {\r\n ArrayList<Integer> path = new ArrayList<>();\r\n path.add(node.data);\r\n return path;\r\n }\r\n\r\n for (Node child : node.children) {\r\n ArrayList<Integer> ptc = nodeToRootPath(child, data);\r\n if (ptc.size() > 0) {\r\n ptc.add(node.data);\r\n return ptc;\r\n }\r\n }\r\n\r\n return new ArrayList<>();\r\n }\r\n\r\n public static int lca(Node node, int d1, int d2) {\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 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 d1 = Integer.parseInt(br.readLine());\r\n int d2 = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n int lca = lca(root, d1, d2);\r\n System.out.println(lca);\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 if root.data == val:\r\n \r\n base_ans = []\r\n base_ans.append(root.data)\r\n return base_ans\r\n\r\n \r\n for child in root.children:\r\n pt = nodeToRootPath(child,val)\r\n \r\n if len(pt) > 0:\r\n pt.append(root.data)\r\n return pt\r\n \r\n way = []\r\n return way\r\n\r\ndef lca(root, data1, data2):\r\n \r\n # Write your code here\r\n \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 \r\n data1 = int(input())\r\n data2 = int(input())\r\n \r\n root = constructor(lst, n)\r\n ans = lca(root, data1, data2)\r\n print(ans)"}},"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\r\n80","sampleOutput":"80","questionVideo":"https://www.youtube.com/embed/5xlRdBskWJE","hints":[],"associated":[{"id":"07507a66-eb76-4348-8c5f-f47c21f65a24","name":"Is the function nodeToRootPath helpful for this question ?","slug":"is-the-function-nodetorootpath-helpful-for-this-question","type":4},{"id":"737994bf-b97b-4695-8916-f4487d943745","name":"What is the space complexity of \"Lowest common ancestor-Generic tree\"?","slug":"what-is-the-space-complexity-of-lowest-common-ancestor-generic-tree","type":4},{"id":"a467d46e-3d47-4573-ab78-3b9628cc856d","name":"What is the time complexity of \"Lowest common ancestor-Generic tree\"?","slug":"what-is-the-time-complexity-of-lowest-common-ancestor-generic-tree","type":4},{"id":"bb763ec3-1548-49f8-b875-0582ccf0bbce","name":"Two pointers are initialized at which place ?","slug":"two-pointers-are-initialized-at-which-place","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":"9f32a8b3-b329-4ae4-b666-1ef8f644bd13","name":"Lowest Common Ancestor (generic Tree)","slug":"lowest-common-ancestor-generic-tree","type":1}],"next":{"id":"e54f1209-5cb9-47aa-9892-9f9161819a8e","name":"Lowest Common Ancestor - Generic Tree","type":3,"slug":"lowest-common-ancestor-generic-tree"},"prev":{"id":"1513c0cf-08a6-4053-8539-befcbff18990","name":"Node To Root Path In Generic Tree","type":3,"slug":"node-to-root-path-in-generic-tree"}}}
plane

Editor

Loading...

Lowest Common Ancestor (generic Tree)

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of lca function. The function is expected to return the lowest common ancestor of two data values that are passed to it. Please watch the question video to understand what lca is. 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 80

Sample Output

80

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode