Lowest Common Ancestor of 2 given nodes in the BST


  • 0
    S

    We will start traversing from the root node 'r' of the Binary Search Tree(BST).
    Let v and w be the nodes we are looking the LCA for.
    We assume v and w will be present in the BST.

    Note : In a BST, if node n1 is greater than node n , it will be to the right of n and if its smaller than n, it will be to the left of n.
    We can use this property and traverse recursively from root to look for LCA of v and w.

    If v and w are greater than r, we will traverse recursively to the right.
    If v and w are smaller than r, we will traverse recursively to the right.
    Else, root is the LCA.

    # Function to find LCA of v and w. 
    def lca(root, v, w):
         
        # Base Case
        if root is None:
            return None
     
        # If both v and w are smaller than root, then LCA lies in left
        if(root.data > v and root.data > w):
            return lca(root.left, v, w)
     
        # If both v and w are greater than root, then LCA lies in right 
        if(root.data < v and root.data < w):
            return lca(root.right, v, w)
     
        return root
    

  • 0
    F

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null || p == null || q == null) 
            return null;
        if(root == p) return p;
        if(root == q) return q;
        
        boolean pIsRigth = checkChildren(root.right, p);
        boolean qIsLeft  = checkChildren(root.left, q);
        
        if((pIsRigth && qIsLeft) || (!pIsRigth && !qIsLeft))
            return root;
        else {
            
            if(pIsRigth && !qIsLeft)
                return lowestCommonAncestor(root.right, p, q);
            else 
                return lowestCommonAncestor(root.left, p, q);
            
        }
    }
    
    public boolean checkChildren(TreeNode root, TreeNode n) {
        if(root == null)
            return false;
        if(root == n)
            return true;
        return checkChildren(root.left, n) || checkChildren(root.right, n);
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.