Lowest Common Ancestor

Problem Statement: Given a binary tree and two nodes A, B, find the lowest common ancestor. Assume a node is descant of itself.

There are 3 kinds of situations how A and B reside in the binary tree:

1. A and B are separated in left subtree and right subtree of the root. The LCA is the root.

   

2. A or B is the root. The LCA is the root.

   

3. A and B are in both left subtree or right subtree. The LCA is is in corresponding subtree. Just recursively call the function and assign root to be the root of left subtree or right subtree.

   

LintCode Problem: Lowest Common Ancestor

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        // Deal with null root and situation #2
        if (root == null || A == root || B == root)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);

        // situation #1: A and B are in different subtrees of root 
        if (left != null && right != null)
            return root;
        // situation #3: A and B are in same side
        else if (left != null)
            return left;
        else if (right != null)
            return right;
        // Help to handle situation #3
        else
            return null;
    }

When TreeNodes have parent reference/pointer:

Firstly get the depth of A and B, assume B has larger depth. Let B traverses up till it reaches A's depth. Then, make A and B traverse up together, till get match TreeNode.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {

        if (root == null || A == root || B == root)
            return root;

        // Obtain two nodes' depth
        int depth_A = depth(root, A);
        int depth_B = depth(root, B);

        if (depth_A > depth_B)
            return lowestCommonAnscetor(root, B, A);
        // Make two nodes in same depth
        int difference = depth_A - depth_B;
        for (int i=0; i<difference; i++){
            B = B.parent;
        }
        // Traverse up the tree till found same node or reach the root
        while (A && B){
            if (A == B)
                return A;
            else{
                A = A.parent;
                B = B.parent;
            }
        }
        // When one of nodes not exist
        return null;

    }

// Help to calculate TreeNode's depth
private int depth(TreeNode root, TreeNode node){
    if (node == root)
        return 0;
    return 1+depth(root, node.parent);
}

Find LCA of nodes in Binary Search Tree:

Easier version of LCA problem, only need to compare the values of nodes with root. Still remain the three situations.

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // When null root and situation #2
        if (root == null || p == root || q == root)
            return root;

        if (p.val > q.val)
            return lowestCommonAncestor(root, q, p);
        // Situation #3
        if (q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        if (p.val > root.val)
            return lowestCommonAncestor(root.right, p, q);
        // Situation #1
        if (p.val < root.val && q.val > root.val)
            return root;

        return null;
    }