How to Implement the Lowest Common Ancestor in a Binary Tree Algorithm

Introduction

Finding where two nodes in a binary tree converge in their ancestry is a problem that often arises when analyzing hierarchical data. This node, the one farthest from the root that is still a shared ancestor of both nodes, is what we call the Lowest Common Ancestor (LCA). It serves as a bridge point in the tree where two paths meet, and identifying it is useful in a wide range of tree-based applications.

Concept Overview of Lowest Common Ancestor

Let’s define the challenge: You’re given a binary tree and two nodes within it. These nodes can appear anywhere in the structure, and there’s no ordering rule like in a binary search tree. Your task is to find the node that is the deepest shared parent of both.

Visually, picture this scenario:

mathematicaCopiaModifica        A
       / \
      B   C
     / \   \
    D   E   F
       /
      G

If we’re looking for the LCA of G and D we trace their ancestry back and find that B is the first common node on both paths.

Solution of the Lowest Common Ancestor Algorithm

The method we’ll use is recursive. We look through the tree, starting from the root, and we apply the following logic:

• If the current branch ends (i.e., the node is null), we return nothing.
• If the node matches either of the target nodes, we send it up the call stack.
• Otherwise, we check both the left and right subtrees.
• If both subtrees return results, it means each target was found on a different side — making the current node their LCA.
• If only one side returns a non-null result, that means both targets are deeper down that branch.

Java Implementation of the Lowest Common Ancestor Algorithm

Below is a Java implementation that applies this logic:

public class LowestCommonAncBinTree {

    public TreeNode lCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode leftLCA = lCA(root.leftNode, p, q);
        TreeNode rightLCA = lCA(root.rightNode, p, q);

        if (leftLCA != null && rightLCA != null) {
            return root;
        }

        return (leftLCA != null) ? leftLCA : rightLCA;
    }

    public static void main(String[] args) {
        LowestCommonAncBinTree tree = new LowestCommonAncBinTree();

        LowestCommonAncBinTree.TreeNode root = tree.new TreeNode(3);
        root.leftNode = tree.new TreeNode(5);
        root.rightNode = tree.new TreeNode(1);
        root.leftNode.leftNode = tree.new TreeNode(6);
        root.leftNode.rightNode = tree.new TreeNode(2);
        root.rightNode.leftNode = tree.new TreeNode(0);
        root.rightNode.rightNode = tree.new TreeNode(8);
        root.leftNode.rightNode.leftNode = tree.new TreeNode(7);
        root.leftNode.rightNode.rightNode = tree.new TreeNode(4);

        TreeNode p = root.leftNode; // Node 5
        TreeNode q = root.rightNode; // Node 1

        TreeNode lca = tree.lCA(root, p, q);
        System.out.println("Lowest Common Ancestor of " + p.nodeVal + " and " + q.nodeVal + " is: " + lca.nodeVal);
    }
    
    class TreeNode {
        int nodeVal;
        TreeNode leftNode;
        TreeNode rightNode;

        TreeNode(int nodeVal) {
            this.nodeVal = nodeVal;
        }
    }
    
}

Conclusion

This approach works efficiently by exploring each node once, giving it a linear runtime with respect to the number of nodes in the tree. It’s versatile enough to handle any binary tree structure and doesn’t depend on the values of the nodes. Whether you’re working on tree structures in software architecture, genealogy, or file systems, understanding and implementing LCA logic is a valuable skill.

You can find the example code on Github.