Lowest Common Ancestor: recursive: if left and right both non-null, current is LCA

• Lowest Common Ancestor (LCA) is the deepest node whose subtree contains both target nodes.
• Post-order recursion searches the tree once, with each call returning a signal about what it found.
• Base case returns the node itself if it is null or if it equals either target.
• Split rule says if both left and right return non-null, the current node is the LCA.
• Propagation passes up the non-null result when only one side found a target.
• Time is O(n); space is O(h) for the call stack.

What is the Lowest Common Ancestor problem?

The Lowest Common Ancestor of two nodes p and q in a binary tree is the deepest node that has both p and q as descendants (where a node can be a descendant of itself). This is a fundamental tree problem used in hierarchy auditing, conflict-of-interest checks, and organizational reporting.

package com.bank.service;

public class ConflictOfInterestService {
    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;
    }
}

Why does this problem matter in banking systems?

At the National Bank of India, when two employees are involved in the same transaction, the compliance team needs to find the lowest-level manager who oversees both. That manager is accountable for any conflict of interest. The LCA algorithm gives this answer in a single pass through the hierarchy.

How does the post-order recursion work?

The elegance is that a single post-order traversal answers the question without storing paths. Each recursive call returns a node that signals what it found in its subtree.

The base case returns the current node if it is null or if it equals either target. Returning the target itself is the signal that this subtree contains a target.

// Base case: null or found a target
if (root == null || root == p || root == q) return root;

The recursive case searches both children:

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

The decision is based on what the two sides report:

// Both sides found something: current node is the LCA
if (left != null && right != null) return root;

// Only one side found something: propagate it up
return left != null ? left : right;

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

LCA(5, 1) = 3  (5 found on left, 1 found on right)
LCA(5, 4) = 5  (5 is returned as base case, 4 is in its subtree)
LCA(7, 4) = 2  (7 found on left of 2, 4 found on right of 2)

How does the split rule identify the LCA?

When both the left and right recursive calls return non-null, it means one target was found in the left subtree and the other in the right subtree. The current node is the point where the two targets diverge, making it the deepest ancestor that contains both. No deeper node can contain both because they are in separate branches.

// Trace for LCA(7, 4) on the tree above:
// At node 2: left=7 (found 7), right=4 (found 4)
// Both non-null → node 2 is the LCA
// At node 5: left returns 2 (the LCA), right returns null
// Only left is non-null → propagate 2 up
// At node 3: left returns 2, right returns null
// Only left is non-null → propagate 2 up
// Final answer: node 2

What if one target is an ancestor of the other?

If p is an ancestor of q, then the recursion at p returns p immediately as the base case (since root == p). The search for q never needs to happen because p itself is the LCA. This case falls out naturally from the base case without special handling.

// LCA(5, 4) on the tree above:
// At node 5: root == p, so return 5 immediately
// The recursion does not descend to find 4
// Node 5 is correctly returned as the LCA

How is this different from LCA in a BST?

In a BST, the ordering property lets you walk down from the root in O(h) time. If both targets are smaller, go left. If both are larger, go right. The first node where they split is the LCA. The general binary tree algorithm does not use ordering and must visit O(n) nodes in the worst case.

| Aspect | General Binary Tree LCA | BST LCA |
|--------|------------------------|---------|
| Uses ordering | No | Yes |
| Time | O(n) | O(h) |
| Approach | Post-order recursion | Walk down from root |
| Works on any tree | Yes | Only BST |

// BST LCA (more efficient for BSTs)
public TreeNode lcaBST(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;  // split point is the LCA
        }
    }
    return null;
}

What are edge cases?

• One target is the root: the root is the LCA.
• Both targets are the same node: that node itself is the LCA.
• One target is a direct child of the other: the parent target is the LCA.
• The tree has only one node that is both p and q: return that node.

// Edge case: p is the root
// LCA(3, 4) on the tree above = 3
// Because 3 is returned at the base case

What if one target does not exist in the tree?

The simple algorithm assumes both targets exist. If one might be absent, the algorithm can mistakenly return the present node as if it were the LCA. A stricter version continues searching after finding one target and confirms that both were actually found before declaring an ancestor.

// Strict LCA: confirms both nodes exist
public TreeNode lcaStrict(TreeNode root, TreeNode p, TreeNode q) {
    boolean[] found = new boolean[2];  // found[0]=p, found[1]=q
    TreeNode result = lcaHelper(root, p, q, found);
    return (found[0] && found[1]) ? result : null;
}

What are common mistakes?

The first mistake is checking root.val == p.val instead of root == p, which can match the wrong node if values are not unique. The second mistake is forgetting to search both subtrees when only one side returns null, leading to a premature null return.

// WRONG: value comparison instead of reference
if (root.val == p.val) return root;  // may match wrong node

// CORRECT: reference comparison
if (root == p) return root;

What should a senior engineer know?

The algorithm runs in O(n) time and O(h) space. The assumption that both nodes exist is critical. In production at the National Bank of India, Rajesh added a pre-check that both target employees exist in the hierarchy before running the LCA query, and logged the result with both employee IDs and the manager's position for the compliance audit trail.