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

Sort by

recency

|

10 Discussions

|

  • vadym_usatiuk
     + 0 comments

    Java 7 O(n)

    public static Node lca(Node root, int v1, int v2) {
            while (root != null) {
                if (root.data > v1 && root.data > v2) {
                    root = root.left;
                } else if (root.data < v1 && root.data < v2) {
                    root = root.right;
                } else {
                    return root;
                }
            }
            return null;
        }

  • starobinetsjose1
     + 0 comments

    Python. Should work for any tree not only binary search.

    def search(root, v):
    if root:
        if root.info == v:
            return root
        l = search(root.left, v)
        if l:
            return l
        r = search(root.right, v)
        if r:
            return r
        return None
            
def lca(root, v1, v2):

    if search(root.left, v1) and search(root.left, v2):
        return lca(root.left, v1, v2)
    
    if search(root.right, v1) and search(root.right, v2):
        return lca(root.right, v1, v2)
    
    return root

  • starobinetsjose1
     + 0 comments

    Python

    def lca(root, v1, v2):
    if v1<root.info and v2<root.info:
        return lca(root.left,v1,v2)
    if v1>root.info and v2>root.info:
        return lca(root.right,v1,v2)
    return root

  • raazi_sheikh
     + 0 comments

    C++

    Node *lca(Node *root, int v1,int v2) {
		// Write your code here.
        if(root==NULL)
            return NULL;
        if(root->data==v1 || root->data==v2)
            return root;
        Node* lca1=lca(root->left, v1, v2);
        Node* lca2=lca(root->right, v1, v2);
        if(lca1!=NULL &&lca2!=NULL)
            return root;
        else if(lca1!=NULL)
            return lca1;
        else
            return lca2;
    }

  • 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;
    }