Lowest Common Ancestor of a Binary Tree

The lowest common ancestor (LCA) problem requires identifying the deepest node that has both target nodes as descendants in a binary tree structure.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we assume that both nodes p and q exist in the tree? Or should we handle cases where one or both might not be present?
2. Are node values guaranteed to be unique? If not, how should we handle duplicate values?
3. Is the tree a binary search tree (BST), or is it just a general binary tree?
4. Can we modify the input tree structure, or must we work with it as-is?
5. What is the expected time complexity for the solution? Should we aim for O(n) or better?

Restatement of the problem: Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA). The LCA is defined as the deepest node that has both p and q as descendants (where a node can be a descendant of itself).

Input/output specification:

• Input: Root of a binary tree, and two TreeNode objects p and q
• Output: TreeNode representing the LCA node

Constraints:

• The tree can have up to 10^4 nodes
• Node values are in the range [-10^9, 10^9]
• All node values are unique (assumption based on typical problem constraints)
• Both p and q exist in the tree

Assumptions made:

1. The input is a valid binary tree with proper parent-child relationships
2. Both p and q nodes exist in the tree (we don't need to handle missing nodes)
3. Node values are unique (standard assumption for this problem)
4. We can modify the tree structure during our solution process if needed

Data shape and hidden structure: The problem involves a hierarchical tree structure where each node has at most two children. The key insight is that the LCA must be a node where:

1. Both p and q are in its subtree (or one of them is the node itself)
2. The path from root to p and q diverges at this node
3. This creates a "split" point in the traversal paths, which is the LCA

The structure suggests we're looking for a path-based solution or a recursive approach that can traverse the tree and identify when both target nodes are found in different subtrees of a given node.

2. Pattern Recognition

The problem asks us to find the lowest common ancestor (LCA) of two nodes in a binary tree. This is a classic pattern that appears frequently in tree algorithms and graph traversal problems.

Most likely patterns:

1. Tree Traversal with Path Tracking - We need to find paths from root to both target nodes
2. Recursive Tree Decomposition - The LCA must be found by recursively examining subtrees
3. Parent-Child Relationship Analysis - The solution involves understanding how nodes relate to each other in the tree structure

Wording that signals the pattern:

• "Lowest Common Ancestor" - This is a standard term for a well-known tree problem pattern
• "Binary Tree" - Indicates we're working with a hierarchical data structure where parent-child relationships exist
• "Two nodes" - Signals we need to compare or trace paths from root to multiple targets

Why this fits the pattern: This problem is fundamentally about finding a shared structural relationship in a hierarchical data structure. The key insight is that the LCA is the deepest node that has both target nodes in its subtree. This pattern appears in many interview problems involving tree navigation, path finding, and hierarchical data structures.

Core insight: The LCA can be found by either:

1. Finding paths from root to each target node and comparing them, or
2. Using recursive decomposition where we traverse the tree and return the first node that has both targets in its subtrees

The most elegant approach uses recursive tree decomposition, which is the pattern that will guide our solution design.

3. Approach Evolution

My first instinct is to use a recursive approach because this problem naturally decomposes into subproblems - if I can find the LCA of left and right subtrees, I can build up to the full solution. But that approach would be O(n²) in worst case because for each node, I'd have to traverse down to find the target nodes again.

Let me think about how to optimize this. I notice that if I can find both target nodes in the tree and track their paths from root, I can reduce it to O(n) time. Actually, even better - if I think about this more carefully, I can do it in one pass with O(n) time and O(h) space where h is the height.

The key insight is that once I find one of the target nodes, I can return it up the recursion stack. If both left and right subtrees return non-null values, then the current node is the LCA. If only one side returns a value, that's the LCA.

I'm going to use a recursive approach where:

1. If current node is null or matches either target, return it
2. Recursively search left and right subtrees
3. If both left and right return non-null values, current node is LCA
4. Otherwise return whichever subtree returned a valid node

This approach maintains the invariant that we're always returning either:

• A target node (if found in subtree)
• The LCA node (if both targets found in different subtrees)
• Null (if neither target found in subtree)

The optimization here is that we don't need to track paths or do multiple traversals - we can determine the LCA in a single pass by leveraging the recursive structure and returning early when we find one of the targets.

This is better than O(n²) because we only visit each node once, and the recursion stack depth is at most O(h) where h is tree height.

4. Data Structure Choice

For the Lowest Common Ancestor (LCA) problem, I'll use a combination of standard tree node structures and auxiliary data to optimize the solution.

Primary Data Structures

1. TreeNode Class (Standard Binary Tree Node)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

This is the standard representation for binary tree nodes. It's essential because:

• It maintains the tree structure needed for traversal
• It provides the basic building block for our algorithm
• It's immutable in structure (we're not modifying the tree itself)

2. HashMap for Parent Tracking

Map<TreeNode, TreeNode> parentMap = new HashMap<>();

This is used to store each node's parent reference, enabling upward traversal from any node to root.

Why These Structures Are Needed

The HashMap is crucial for the optimized O(n) solution approach where we:

• Precompute parent relationships in O(n) time
• Allow us to traverse upward from either target node to root
• Enable us to find intersection point of two paths

Time and Space Impact

Time Complexity:

• HashMap population: O(n) - we visit each node once
• LCA lookup: O(h) where h is height (O(log n) for balanced trees)
• Overall: O(n) for preprocessing + O(h) for query

Space Complexity:

• HashMap storage: O(n) - one entry per node
• Recursive call stack: O(h) - maximum depth of recursion
• Total: O(n) space

Helper Structures

HashSet for Path Tracking

Set<TreeNode> ancestors = new HashSet<>();

This is used in the second approach to track visited nodes during upward traversal, making it easy to detect when we encounter a node that's also in the other path.

The combination of these structures provides clean, efficient implementation while maintaining the algorithm's optimal complexity characteristics. The HashMap enables O(1) parent lookups, and HashSet provides O(1) membership testing for our path intersection logic.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

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

// Find LCA of nodes 5 and 1

Step-by-step execution:

1. Initial call: lowestCommonAncestor(root, 5, 1)

   • Node 3 (root) is not null, so we proceed
   • Check if root == 5 or root == 1 → No match

2. Recursive left call: lowestCommonAncestor(root.left, 5, 1) where root.left = node 5

   • Node 5 matches target 5, so return node 5

3. Recursive right call: lowestCommonAncestor(root.right, 5, 1) where root.right = node 1

   • Node 1 matches target 1, so return node 1

4. Back to root level:

   • Left subtree returned node 5 (not null)
   • Right subtree returned node 1 (not null)
   • Since both are non-null, root node 3 is the LCA

Key execution points:

• When a node matches one of our targets, we return that node
• When both left and right subtrees return non-null values, the current node is the LCA
• The algorithm efficiently prunes paths once a match is found

Edge case handling:

• If one node is ancestor of another, the deeper node will return null from one side
• The first node that has both targets in different subtrees becomes the LCA

The algorithm terminates correctly because:

1. Each node is visited at most once
2. The recursive structure ensures we find the lowest common ancestor by checking all paths
3. When both target nodes are found in different subtrees, we've identified the LCA

6. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode result;
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        result = null;
        dfs(root, p, q);
        return result;
    }
    
    /**
     * Returns true if the subtree rooted at 'node' contains either p or q or both.
     * When we find a node that has both p and q in its subtrees (or one of them 
     * at the node itself), we set it as the LCA.
     */
    private boolean dfs(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return false;
        }
        
        // Check if current node is one of the target nodes
        boolean isCurrent = (node == p || node == q);
        
        // Recursively check left and right subtrees
        boolean left = dfs(node.left, p, q);
        boolean right = dfs(node.right, p, q);
        
        // If we found both p and q in different subtrees (or one at current node),
        // then current node is the LCA
        if ((left && right) || (isCurrent && (left || right))) {
            result = node;
        }
        
        // Return true if current subtree contains p or q
        return left || right || isCurrent;
    }
}

This solution uses a single DFS traversal to find the LCA in O(n) time. The key insight is that we can determine if a node is the LCA by checking whether both target nodes exist in its left and right subtrees, or one of them is the current node and the other is in one of its subtrees. The algorithm avoids storing paths or using parent pointers, making it both time and space efficient.

7. Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the binary tree. In the worst case, we might need to visit all nodes to find the LCA. The algorithm performs a single traversal of the tree, and each node is processed once.

Space Complexity: O(H) where H is the height of the binary tree. This space is used for the recursion stack during the depth-first search traversal. In the worst case (skewed tree), H = N, making space complexity O(N). For a balanced tree, H = O(log N).

The time complexity is optimal because we must examine each node at least once in the worst case to determine the LCA. The space complexity is also optimal for recursive approaches, as we must maintain the call stack to track our path through the tree.

The solution is optimal because:

1. It makes exactly one pass through the tree
2. It uses minimal additional space proportional to the recursion depth
3. It avoids redundant traversals or preprocessing steps that would increase time complexity

This is the best possible complexity for this problem when using a recursive approach, as we must examine each node to determine the LCA relationship between the two target nodes.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty tree: When root is null, the method should return null or handle gracefully
• Single node: When tree has only one node, both target nodes could be the same node
• One node is ancestor of another: When one node is directly or indirectly parent of the other

Duplicate Values and Repeated States

• Duplicate node values: The problem assumes unique values, but if duplicates exist, the algorithm must still work correctly by identifying nodes by reference, not value
• Same target node: If both p and q refer to the same node, LCA is that node itself

Boundary Conditions

• Target nodes not in tree: If either p or q does not exist in the tree, behavior should be well-defined (typically return null)
• Root node as LCA: When one target is root and another is in its subtree, root is the correct answer
• Both nodes in same subtree: When both targets are in left or right subtree, LCA is the deepest node that contains both

Common Implementation Mistakes

• Not handling null returns properly: A common mistake is not checking if recursive calls return null, leading to NullPointerExceptions
• Incorrect base case handling: Failing to properly handle the case where root equals p or q before making recursive calls
• Overwriting result variables: When using a shared variable to track found nodes, overwriting can occur if not careful about the search termination condition
• Not returning early: When both left and right subtrees return non-null values, the current node should be returned immediately without further processing

Implementation-specific Issues

• Modifying input tree: If the algorithm tries to modify the tree structure (e.g., setting child pointers to null), it breaks the contract
• Stack overflow: With very deep trees, recursive approaches might cause stack overflow; iterative solutions would be preferred in such cases
• Incorrect return logic: Returning the wrong node when both left and right subtrees contain targets (should return current root, not one of the subtrees)

9. Alternative Approaches

There are several alternative approaches to solving the LCA problem, each with different trade-offs:

Approach 1: Parent Pointers If the tree nodes had parent pointers, we could traverse upward from both nodes to find their intersection. This would involve:

• Store all ancestors of one node in a set
• Traverse upward from the second node until we find an ancestor in the set
• Time: O(h) where h is height, Space: O(h)

Approach 2: Path to Nodes We could find the path from root to each target node, then compare these paths to find the last common node:

• Find path from root to p and root to q
• Compare paths element by element until they diverge
• Time: O(n), Space: O(n) for storing paths

Approach 3: DFS with Node Counting Instead of returning boolean flags, we could count how many target nodes are found in each subtree:

• Return a count of how many target nodes exist in the current subtree
• When count becomes 2, we've found our LCA
• Time: O(n), Space: O(h) for recursion stack

Trade-offs Analysis: The chosen approach (post-order traversal with early termination) is preferred because:

• It's more intuitive and readable
• It avoids storing additional path information
• It handles the case where one node is descendant of another elegantly
• The recursion-based solution naturally fits the tree structure

The parent-pointer approach is more efficient for multiple queries but requires modifying the tree structure. The path-based approach uses more space and is less elegant for the single-query case.

The DFS counting approach works but requires more careful handling of edge cases and is less intuitive than the current solution.

10. Test Cases

// Test case 1: Basic case with valid LCA
// Input tree:     3
//                / \
//               5   1
//              / \ / \
//             6  2 0  8
//               / \
//              7   4
// LCA(5,1) = 3, LCA(6,4) = 5
TreeNode root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

// Test case 2: One node is ancestor of another
// LCA(5,4) = 5 (node 5 is ancestor of node 4)
assert solution.lowestCommonAncestor(root, root.left, root.left.right.right) == root.left;

// Test case 3: Same node
// LCA(5,5) = 5
assert solution.lowestCommonAncestor(root, root.left, root.left) == root.left;

// Test case 4: Empty tree
// LCA(null, null) = null
assert solution.lowestCommonAncestor(null, null, null) == null;

// Test case 5: Single node tree
// Input: [1], p=1, q=1
TreeNode single = new TreeNode(1);
assert solution.lowestCommonAncestor(single, single, single) == single;

// Test case 6: Nodes not in tree
// LCA(9,8) where 9 doesn't exist - should return null or handle gracefully
// This would require additional validation logic in the implementation

// Test case 7: Root node as LCA
// LCA(6,0) = 3 (root)
assert solution.lowestCommonAncestor(root, root.left.left, root.right.left) == root;

The test cases cover:

• Basic valid LCA scenarios with proper tree structure
• Edge case where one node is ancestor of another
• Same node as both parameters
• Empty tree and single node edge cases
• Boundary condition where nodes are on opposite sides of root
• Invalid input handling (though this would require additional validation logic in the implementation)

11. Final Summary

The core idea is to find the lowest common ancestor by leveraging the tree's hierarchical structure and parent-child relationships. This solution works efficiently by traversing the tree once to build parent mappings and depths, then aligning the two target nodes at the same level before moving them upward in lockstep until they meet at their LCA. The approach is optimal because it achieves O(n) time complexity with a single pass to build the parent map and O(h) space complexity where h is the tree height, making it highly efficient for large binary trees. The solution's elegance lies in its use of the depth property to eliminate the need for complex path tracking or multiple traversals.