Lowest Common Ancestor

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

        4

/     \

3         7

/     \

5         6

For 3 and 5, the LCA is 4.

For 5 and 6, the LCA is 7.

For 6 and 7, the LCA is 7.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
    if (root == null || root == A || root == B) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, A, B);
    TreeNode right = lowestCommonAncestor(root.right, A, B);

    //both left and right are not null,
    //means A and B have to be in each of the subtrees
    if (left != null && right != null) {
        return root;
    }
    //if only left or right is not null,
    //means both A and B are in same subtree
    if (left != null) {
        return left;
    }
    if (right != null) {
        return right;
    }
    return null;
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *