Binary Search Tree : Lowest Common Ancestor

  • + 68 comments

    Solution is based on the following thought: The value of a common ancestor has to always be between the two values in question.

    static Node lca(Node root,int v1,int v2)
    {
        //Decide if you have to call rekursively
        //Samller than both
        if(root.data < v1 && root.data < v2){
            return lca(root.right,v1,v2);
        }
        //Bigger than both
        if(root.data > v1 && root.data > v2){
            return lca(root.left,v1,v2);
        }
    
        //Else solution already found
        return root;
    }