Understanding Lowest Common Ancestor (LCA) in Java

Introduction & Problem Explanation

The Lowest Common Ancestor (LCA) of two nodes p and q in a binary tree is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

For example, in a tree with root 3, and child nodes p = 5 and q = 1, the LCA is the root 3 itself because both nodes diverge from it. If p = 5 and q = 4 (where 4 is a child of 5), the LCA is 5. This algorithm is widely used in relational databases, organization chart software, and inheritance mapping compilers.

The Algorithmic Approach

1. Post-Order Recursive DFS Search (O(n) Time, O(h) Space)

We traverse the tree recursively. For any given node:

• If the current node is null, or equals either p or q, we return the current node. This represents finding one of our target nodes or hitting a leaf boundary.
• We recursively search the left subtree: TreeNode left = lowestCommonAncestor(root.left, p, q).
• We recursively search the right subtree: TreeNode right = lowestCommonAncestor(root.right, p, q).
• If both left and right search results are non-null, it means one target node was found in the left subtree and the other was found in the right subtree. Therefore, the current node is their split point, which makes it the LCA.
• If only one of them is non-null, it means both target nodes reside in that non-null subtree, so we pass that result up to the parent caller.

This traverses each node once, giving O(n) time complexity. The space complexity is O(h) due to the recursion call stack.

Step-by-Step Execution Walkthrough

Let's trace the recursive LCA algorithm on a tree with root 3, left child 5, right child 1. We want to find the LCA of p = 5 and q = 1:

1. Step 1 (Root call): Start at root node 3.
   • We call lowestCommonAncestor(3, 5, 1).
   • Since 3 is not null, and doesn't equal p (5) or q (1), we proceed to search left and right.
2. Step 2 (Search Left Subtree of 3): We call lowestCommonAncestor(3.left, 5, 1) which is lowestCommonAncestor(5, 5, 1).
   • Since the node is 5, which matches p = 5, the base case triggers!
   • The method immediately returns node 5 to the root caller.
3. Step 3 (Search Right Subtree of 3): We call lowestCommonAncestor(3.right, 5, 1) which is lowestCommonAncestor(1, 5, 1).
   • Since the node is 1, which matches q = 1, the base case triggers!
   • The method immediately returns node 1 to the root caller.
4. Step 4 (Resolve at Root 3):
   • We receive left = 5 and right = 1.
   • Since both left and right are non-null, the split point condition matches: if (left != null && right != null) return root;.
   • The root node 3 is returned as the LCA.
5. Step 5 (Completion): The algorithm completes and correctly returns node 3.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• if (root == null || root == p || root == q) return root;: The recursive base case. It stops the search and returns the node as soon as we find either p or q, or hit a leaf.
• if (left != null && right != null) return root;: The core split condition. If both subtrees returned a match, the current node is the lowest common ancestor of the two targets.
• return left != null ? left : right;: If only one subtree returned a match, it means both nodes are on that side, so we bubble that match up.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class LowestCommonAncestor {

    public static class TreeNode {
        public int val;
        public TreeNode left, right;
        public TreeNode(int val) { this.val = val; }
    }

    // Recursive DFS - O(n)
    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;
    }

    public static void main(String[] args) {
        LowestCommonAncestor solver = new LowestCommonAncestor();
        TreeNode root = new TreeNode(3);
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(1);
        root.left = p;
        root.right = q;

        System.out.println("--- Lowest Common Ancestor Demonstration ---");
        TreeNode lca = solver.lowestCommonAncestor(root, p, q);
        System.out.println("LCA Val: " + lca.val);
    }
}

Conclusion

Solving the Lowest Common Ancestor (LCA) problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.