{"id":"205d4872-207e-411a-89c3-997a53ef9ba0","name":"Lca Of Bst","description":"1. You are given a partially written BST class.\r\n2. You are required to complete the body of lca function. \"lca\" function is expected to find the lowest commong ancestor of d1 and d2.\r\n3. Input and Output is managed for you. \r\n\r\nNote -> Please watch the question video for clarity.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nstruct Node{\n int data;\n Node* left;\n Node* right;\n Node(int val){\n data=val;\n left=nullptr;\n right=nullptr;\n }\n};\n\n\nNode* construct(vector<int> & arr){\n Node* root=new Node(arr[0]);\n pair<Node*,int> p={root,1};\n\n stack<pair<Node*,int>> st;\n st.push(p);\n\n int idx=1;\n while(!st.empty()){\n \n if(st.top().second==1){\n st.top().second++;\n if(arr[idx]!=-1){\n st.top().first->left=new Node(arr[idx]);\n pair<Node*,int> lp={st.top().first->left,1};\n st.push(lp);\n }\n else{\n st.top().first->left=nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*,int> rp={st.top().first->right,1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\n\nint ans;\nint lca(Node* root,int a,int b){\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 x;\n cin >> x;\n if(x==\"n\"){\n arr[i]=-1;\n\n }\n else{\n arr[i]=stoi(x);\n }\n }\n int a,b;\n cin >> a >> b;\n Node* root= construct(arr);\n ans=root->data;\n lca(root,a,b);\n cout << ans << endl;\n \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 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 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 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 }\r\n\r\n}"},"python":{"code":"import sys\nimport math\n\nclass Node:\n def __init__(self, key,left,right):\n self.left = left\n self.right = right\n self.val = key\n \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 while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n else:\n st.pop();\n return root; \n \ndef lca(root, n1, n2):\n# Write your code here\n \n\nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\n \nn1=int(input())\nn2=int(input())\n\nroot=construct(arr)\nans = root.val\nlca(root, n1, n2)\nprint(ans)"}},"points":10,"difficulty":"easy","sampleInput":"21\r\n50 25 12 n n 37 30 n n n 75 62 60 n n 70 n n 87 n n\r\n12\r\n30","sampleOutput":"25","questionVideo":"https://www.youtube.com/embed/f7AsXoVNJlQ","hints":[],"associated":[{"id":"2178fffd-70e0-4602-a7d1-aecb853a85b9","name":"If we have to find the lcs of d1 and d2 and the given node data is greater than both d1 and d2, then LCA must lie to the","slug":"if-we-have-to-find-the-lcs-of-d1-and-d2-and-the-given-node-data-is-greater-than-both-d1-and-d2-then-lca-must-lie-to-the","type":4},{"id":"21e60844-4c54-4f56-bfc1-a20555c195bf","name":"What are the worst case and average case complexities of a binary search tree?","slug":"what-are-the-worst-case-and-average-case-complexities-of-a-binary-search-tree","type":4},{"id":"95e07c03-2d0c-4fb4-bdbf-2bd1f6b62b92","name":"What is the lca of 12 and 37 in the given bst?","slug":"what-is-the-lca-of-12-and-37-in-the-given-bst","type":4},{"id":"ec8c4e39-252b-4eb0-b4de-a9d59155ce1e","name":"If the node itself is the lca of d1 and d2, then d1 and d2 must lie","slug":"if-the-node-itself-is-the-lca-of-d1-and-d2-then-d1-and-d2-must-lie","type":4},{"id":"f3bdbeab-6439-4419-bfb5-ff208295cc2e","name":"In the function to find lca, when we get a null node, what should we return to the calling function?","slug":"in-the-function-to-find-lca-when-we-get-a-null-node-what-should-we-return-to-the-calling-function","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":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"2ba13a5b-80d8-4870-bb60-7a0a87d85b42","name":"Lca Of Bst","slug":"lca-of-bst","type":1}],"next":{"id":"51d954e3-2a59-4a94-9754-9262ad919a56","name":"Lca Of Bst","type":3,"slug":"lca-of-bst"},"prev":{"id":"e531028a-ba4c-41a5-b204-50912c7e36b5","name":"Replace With Sum Of Larger","type":3,"slug":"replace-with-sum-of-larger"}}}1. You are given a partially written BST class. 2. You are required to complete the body of lca function. "lca" function is expected to find the lowest commong ancestor of d1 and d2. 3. Input and Output is managed for you. Note -> Please watch the question video for clarity.
{"id":"205d4872-207e-411a-89c3-997a53ef9ba0","name":"Lca Of Bst","description":"1. You are given a partially written BST class.\r\n2. You are required to complete the body of lca function. \"lca\" function is expected to find the lowest commong ancestor of d1 and d2.\r\n3. Input and Output is managed for you. \r\n\r\nNote -> Please watch the question video for clarity.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nstruct Node{\n int data;\n Node* left;\n Node* right;\n Node(int val){\n data=val;\n left=nullptr;\n right=nullptr;\n }\n};\n\n\nNode* construct(vector<int> & arr){\n Node* root=new Node(arr[0]);\n pair<Node*,int> p={root,1};\n\n stack<pair<Node*,int>> st;\n st.push(p);\n\n int idx=1;\n while(!st.empty()){\n \n if(st.top().second==1){\n st.top().second++;\n if(arr[idx]!=-1){\n st.top().first->left=new Node(arr[idx]);\n pair<Node*,int> lp={st.top().first->left,1};\n st.push(lp);\n }\n else{\n st.top().first->left=nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*,int> rp={st.top().first->right,1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\n\nint ans;\nint lca(Node* root,int a,int b){\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 x;\n cin >> x;\n if(x==\"n\"){\n arr[i]=-1;\n\n }\n else{\n arr[i]=stoi(x);\n }\n }\n int a,b;\n cin >> a >> b;\n Node* root= construct(arr);\n ans=root->data;\n lca(root,a,b);\n cout << ans << endl;\n \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 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 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 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 }\r\n\r\n}"},"python":{"code":"import sys\nimport math\n\nclass Node:\n def __init__(self, key,left,right):\n self.left = left\n self.right = right\n self.val = key\n \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 while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n else:\n st.pop();\n return root; \n \ndef lca(root, n1, n2):\n# Write your code here\n \n\nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\n \nn1=int(input())\nn2=int(input())\n\nroot=construct(arr)\nans = root.val\nlca(root, n1, n2)\nprint(ans)"}},"points":10,"difficulty":"easy","sampleInput":"21\r\n50 25 12 n n 37 30 n n n 75 62 60 n n 70 n n 87 n n\r\n12\r\n30","sampleOutput":"25","questionVideo":"https://www.youtube.com/embed/f7AsXoVNJlQ","hints":[],"associated":[{"id":"2178fffd-70e0-4602-a7d1-aecb853a85b9","name":"If we have to find the lcs of d1 and d2 and the given node data is greater than both d1 and d2, then LCA must lie to the","slug":"if-we-have-to-find-the-lcs-of-d1-and-d2-and-the-given-node-data-is-greater-than-both-d1-and-d2-then-lca-must-lie-to-the","type":4},{"id":"21e60844-4c54-4f56-bfc1-a20555c195bf","name":"What are the worst case and average case complexities of a binary search tree?","slug":"what-are-the-worst-case-and-average-case-complexities-of-a-binary-search-tree","type":4},{"id":"95e07c03-2d0c-4fb4-bdbf-2bd1f6b62b92","name":"What is the lca of 12 and 37 in the given bst?","slug":"what-is-the-lca-of-12-and-37-in-the-given-bst","type":4},{"id":"ec8c4e39-252b-4eb0-b4de-a9d59155ce1e","name":"If the node itself is the lca of d1 and d2, then d1 and d2 must lie","slug":"if-the-node-itself-is-the-lca-of-d1-and-d2-then-d1-and-d2-must-lie","type":4},{"id":"f3bdbeab-6439-4419-bfb5-ff208295cc2e","name":"In the function to find lca, when we get a null node, what should we return to the calling function?","slug":"in-the-function-to-find-lca-when-we-get-a-null-node-what-should-we-return-to-the-calling-function","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":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"2ba13a5b-80d8-4870-bb60-7a0a87d85b42","name":"Lca Of Bst","slug":"lca-of-bst","type":1}],"next":{"id":"51d954e3-2a59-4a94-9754-9262ad919a56","name":"Lca Of Bst","type":3,"slug":"lca-of-bst"},"prev":{"id":"e531028a-ba4c-41a5-b204-50912c7e36b5","name":"Replace With Sum Of Larger","type":3,"slug":"replace-with-sum-of-larger"}}}
Editor
Discussions
Show Discussion
Related Resources
