We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<bits/stdc++.h>usingnamespacestd;classNode{public:intdata;Node*left;Node*right;Node(intd){data=d;left=NULL;right=NULL;}};classSolution{public:Node*insert(Node*root,intdata){if(root==NULL){returnnewNode(data);}else{Node*cur;if(data<=root->data){cur=insert(root->left,data);root->left=cur;}else{cur=insert(root->right,data);root->right=cur;}returnroot;}}/*The tree node has data, left child and right child class Node { int data; Node* left; Node* right;};*/vector<int>pathNode(Node*root,intx){vector<int>res;if(!root){returnres;}while(root->data!=x){if(root->data==x){res.push_back(x);returnres;}elseif(root->data>x){res.push_back(root->data);root=root->left;}else{res.push_back(root->data);root=root->right;}}res.push_back(x);returnres;}Node*lca(Node*root,intv1,intv2){// Write your code here.Node*node=root;if(v1>root->data&&v2<root->data){returnroot;}if(v1<root->data&&v2>root->data){returnroot;}vector<int>s1=pathNode(root,v1);vector<int>s2=pathNode(root,v2);inttemp=0;intcount=0;for(inti=s1.size()-1;i>=0;i--){if(count!=0){break;}for(intj=s2.size()-1;j>=0;j--){if(s1[i]==s2[j]){temp=s1[i];count++;break;}}}// cout << temp << endl;while(node->data!=temp){if(node->data==temp){returnnode;}elseif(node->data>temp){node=node->left;}else{node=node->right;}}returnnode;}};//End of Solutionintmain(){SolutionmyTree;Node*root=NULL;intt;intdata;std::cin>>t;while(t-->0){std::cin>>data;root=myTree.insert(root,data);}intv1,v2;std::cin>>v1>>v2;Node*ans=myTree.lca(root,v1,v2);std::cout<<ans->data;return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Binary Search Tree : Lowest Common Ancestor
You are viewing a single comment's thread. Return to all comments →
solution in C++