Lowest Common Ancestor of Two Nodes in a Binary Tree

Any two nodes in a binary tree has the root node as a common ancestor, assuming both nodes are in the same tree. The lower common ancestor node is the furthest node from the root that has both nodes as descendants. The following are two implementations to computing the LCA, one brute force and one optimized.

Brute Force

The brute force approach checks the left subtree and the right subtree at every node. Once it reaches a node where one of the nodes is the root, both nodes are the root, or one node is in the left subtree and the other in the right subtree, the method returns the current node as the LCA. This approach has a time complexity of O(n2).

Implementation

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return null;    
    if (p == root || q == root)
        return root;

    boolean pOnLeft = contains(root.left, p);
    boolean qOnRight = contains(root.right, q);

    if (pOnLeft == qOnRight)
        return root;
    else
        return lowestCommonAncestor(
            (pOnLeft) ? root.left : root.right, p, q
        );
}

Helper Method

private static boolean contains(TreeNode root, TreeNode n) {
    if (root == null)
        return false;
    if (root == n)
        return true;
    return contains(root.left, n) || contains(root.right, n);
}

Optimized

The optimized approach is somewhat similar but makes use of the post order traversal technique and an Data class. As the nodes are visited in post order, it checks whether one of the nodes exists in one of the subtrees, and store that information before returning it to the parent node. This information get percolates up until a node where both nodes are in the subtrees of the current node, the LCA. The time complexity of this approach is O(n) and the space complexity is O(height).

Data Class Definition

class Data {
    int count;
    TreeNode ancestor;

    public Data(int c, TreeNode n) {
        this.count = c;
        this.ancestor = n;
    }
}

Implementation

public static TreeNode lowerCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return null;    
    if (p == root || q == root)
        return root;
    return lowestCommonAncestor(root, p, q).ancestor;
}

public static Data lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return new Data(0, null);

    Data left = lowestCommonAncestor(root.left, p, q);
    if(left.count == 2)
        return left;

    Data right = lowestCommonAncestor(root.right, p, q);
    if(right.count == 2);
        return right;

    int count = left.count + right.count
        + (p == root ? 1 : 0)
        + (q == root ? 1 : 0);

    return new Data(count, (count == 2) ? root : null);
}

This article is my 27th oldest. It is 437 words long, and it’s got 0 comments for now.