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.
  1. Binary Search Tree : Lowest Common Ancestor
  2. Discussions

Binary Search Tree : Lowest Common Ancestor

  • joe_r_2001
     + 0 comments

    c++14 : works for any binary tree (the first example was misleading: i thought we were not dealing with a bst)

    bool trail(Node* root,const int& v,const string& curpath,string& res){
    if(root->data==v) {
        res=curpath;
        return true;
    }
    else if(root->left && root->right) return trail(root->left, v ,curpath+'0',res) || trail(root->right,v,curpath+'1',res);
    else if(root->left) return trail(root->left,v,curpath+'0',res);
    else if(root->right) return trail(root->right,v,curpath+'1',res);
    else return false;
}
Node* traverse(Node* root,const string& path){
    for(const auto& c : path){
        if(c=='0') root=root->left;
        else root=root->right;
    }
    return root;
}
string greatestcommonsubstr(const string& s1,const string& s2){
    string res="";
    for(int i=0;i<s1.size();i++){
        if(s1[i]!=s2[i]) break;
        res+=s1[i];
    }
    return res;
}
    Node *lca(Node *root, int v1,int v2) {
		// Write your code here.
        string pv1;
        string pv2;
        trail(root,v1,"",pv1);
        trail(root,v2,"",pv2);
        root=traverse(root,greatestcommonsubstr(pv1,pv2));
        return root;
    }