Java  

Lowest Common Ancestor in Binary Trees: Easy and Efficient Methods

🌳 What is the Lowest Common Ancestor?

In a binary tree, the Lowest Common Ancestor (LCA) of two given nodes is the deepest node that has both nodes as descendants. This means it’s the shared ancestor located farthest from the root. If one node is an ancestor of the other, it’s also the LCA.

Example:

    3
   / \
  5   1
 / \ / \
6  2 0  8
  / \
 7   4

For nodes 5 and 1, the LCA is 3. For nodes 5 and 4, the LCA is 5.

📜 Problem Statement

Given the root of a binary tree and two nodes p and q, find their Lowest Common Ancestor.

Input: Binary tree root, nodes p and q

Output: The node that is the LCA of p and q.

📏 LCA Rules in Detail

  1. Direct Match: If the current node is p or q, it’s part of the LCA.
  2. Different Subtrees: If p is in one subtree and q is in another, the current node is the LCA.
  3. Same Subtree: If both are in the same subtree, continue searching within that subtree.

🐌 Recursive Approach

We recursively search for p and q. When they’re found in different branches, the current node is the LCA.

Steps:

  • If the current node is null, return null.
  • If the current node is p or q, return the current node.
  • Search recursively in the left subtree.
  • Search recursively in the right subtree.
  • If both left and right calls return non-null - current node is the LCA.
  • If only one side returns non-null - return that side’s result.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Time Complexity: O(n) – where n is the number of nodes.

Space Complexity: O(h) – where h is the tree’s height.

⚡ Optimized Approach for Binary Search Trees (BST)

For BSTs, we can use their ordering property to avoid unnecessary searches.

Steps:

  1. If both p and q are smaller than the root, search the left.
  2. If both are larger, search right.
  3. Otherwise, the root is the LCA.
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        } else {
            return root;
        }
    }
    return null;
}

Time Complexity: O(h) – where h is the height of the tree.
Space Complexity: O(1) – no extra space used.

🧠 Why LCA is Important

  • Helps in network routing to find shortest common paths.
  • Useful in distance calculation between nodes.
  • Applied in hierarchical data systems like organizational charts or genealogy trees.

✅ Conclusion

Understanding the Lowest Common Ancestor is essential for mastering tree algorithms. It builds the foundation for solving complex problems involving paths, distances, and relationships in hierarchical structures. Beginners should start with the recursive approach for any binary tree, then move to the optimized BST method for better performance when applicable.

Membership not found