Lowest Common Ancestor in Binary Search Tree

The lowest common ancestor (LCA) problem in binary search trees leverages the BST property for efficient solution, allowing us to find the deepest node that is an ancestor of both target nodes in O(log n) time.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that both nodes p and q exist in the BST?
2. Can we mutate the input BST structure during our solution?
3. What is the expected return format - should we return the node object or just its value?
4. Are duplicate values allowed in the BST? If so, how should we handle them in our LCA search?
5. What is the target time complexity for follow-up - O(h) where h is height is acceptable or should we aim for better?

Restatement of the pattern:

The Lowest Common Ancestor (LCA) in a Binary Search Tree is the deepest node that has both given nodes p and q as descendants (where a node can be a descendant of itself). In BSTs, we leverage the property that for any node, all values in its left subtree are smaller and all values in its right subtree are larger than the node's value.

Signal words and constraint shape:

Key indicators include "BST", "lowest common ancestor", "two nodes", "find the deepest shared ancestor". The constraint shape is characterized by:

• Sorted structure property (left < node < right)
• Unique node values (typically)
• Tree traversal pattern with predictable ordering

Assumptions:

1. The BST is valid (left < node < right property holds)
2. Both nodes p and q exist in the tree
3. Node values are unique (standard BST assumption)
4. We can safely traverse the tree without modifying structure
5. The LCA is guaranteed to exist

Pattern suitability:

This pattern is best suited for static scenarios where the entire BST structure is available and we're performing multiple LCA queries. It's not ideal for streaming scenarios where nodes are inserted dynamically, as we'd need to rebuild or maintain additional data structures. The BST property makes it particularly efficient for this problem since we can leverage the ordering to avoid full tree traversal.

The core insight is that in a BST, if we traverse from root down to find the LCA, at each step we can determine which direction to go based on comparing node values with the current node's value, making it significantly more efficient than general tree LCA algorithms.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Lowest Common Ancestor" or "LCA" explicitly mentioned
• BST (Binary Search Tree) is specified as input structure
• Two nodes are given to find their LCA in the tree
• Tree is guaranteed to be a valid BST with unique values
• The problem asks for the deepest node that is an ancestor of both input nodes

Why this pattern fits better than the most common alternatives:

• Unlike general tree LCA problems, BST structure allows us to leverage ordering properties for O(log n) search instead of O(n) traversal
• The key insight is that in a BST, if we have two nodes p and q, their LCA will be the first node where one value is less than or equal to the current node and the other is greater than or equal to it
• This is more efficient than storing parent pointers or doing full tree traversal for each node

Conditions where a variation or related pattern applies instead:

• For general trees (not BSTs), we'd need to use parent pointers or path tracking approach
• If the tree is not a BST but we have parent references, we could use the "find path to root" approach
• If we're dealing with a stream of queries on static tree, we might consider Euler tour or binary lifting techniques

The core insight that makes this pattern work:

• In a BST, for any node, all values in left subtree are smaller and all values in right subtree are larger
• If both target nodes p and q are on the same side of current node, we move in that direction
• If they're on different sides (or one equals current node), then current node is the LCA
• This property allows us to eliminate half of the search space at each step, making it O(log n) in balanced trees

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I find the paths from root to each of the two nodes and then compare those paths to find their last common node. But that's O(n²) in worst case because I'd need to traverse the tree multiple times and store paths. Let me think about how to optimize this.

I notice that if I leverage the BST property where for any node, all values in left subtree are smaller and all values in right subtree are larger, I can do better than storing complete paths. If I'm looking for LCA of nodes p and q, and I'm at current node curr:

• If both p and q are smaller than curr.val, I know the LCA must be in left subtree
• If both p and q are larger than curr.val, I know the LCA must be in right subtree
• If one is smaller and one is larger, or if curr.val equals either p or q, then curr is the LCA

This approach reduces to O(h) where h is height of tree, and I don't need to store paths or do multiple traversals. The key insight is that the BST property gives us directional information to navigate directly to the answer.

Let me trace through this logic more carefully to make sure I'm not missing edge cases.

Brute-force approach and why it is not ideal:

The naive approach would be to:

1. Find path from root to node p
2. Find path from root to node q
3. Compare paths to find last common element

This requires:

• Two separate traversals (O(n) each)
• Path storage (O(n) space)
• Path comparison (O(n) time)

This is inefficient because we're doing redundant work - we don't need to store the entire paths, just the common ancestry.

Improved approach and the key optimization:

The key optimization is leveraging BST properties:

• Instead of storing paths, we can navigate the tree directly using the ordering property
• At each node, we can determine which direction to go based on comparing values with p and q
• We don't need to find complete paths - we can stop as soon as we find the LCA

Final approach with step-by-step reasoning:

1. Start at root node
2. For current node curr:
   • If both p and q are less than curr.val, move to left child
   • If both p and q are greater than curr.val, move to right child
   • Otherwise (one is less, one is greater, or curr matches p/q), curr is LCA
3. Continue until we find the LCA

Important invariants that must hold:

• At any point, if we're at node curr, either both p and q are in left subtree, or both in right subtree, or one is equal to curr and the other is in either subtree
• The algorithm maintains that we're always moving toward the LCA or have found it
• We never visit nodes that cannot possibly contain the LCA

4. Data Structure Choice

For the Lowest Common Ancestor (LCA) in BST problem, the primary data structure is a Binary Search Tree node structure.

Primary Data Structures Used

1. BST Node Class:

   • Contains val, left, and right fields
   • Provides the fundamental structure to navigate the tree
   • Allows for leveraging BST properties (left subtree < node < right subtree)

2. Reference Pointers:

   • Pointers to p and q nodes (the target nodes for which we find LCA)
   • Pointers to current traversal node during algorithm execution

Why Each Data Structure Is Needed

The BST node structure is essential because:

• It provides the tree traversal capability needed to navigate from root to target nodes
• It enables leveraging BST properties for optimization (no need to search entire tree)
• It allows us to maintain parent-child relationships required for LCA determination

Reference pointers are needed because:

• They track the target nodes p and q throughout the traversal
• They enable us to compare node values efficiently during traversal
• They allow for in-place traversal without requiring additional data structures

Time and Space Impact

Time Complexity: O(1) for node access, O(h) for traversal where h is height Space Complexity:

• O(1) additional space for the algorithm itself (excluding recursion stack)
• O(h) space for recursive call stack in worst case (skewed tree)
• O(1) space if iterative approach is used

Helper Structures

No additional helper data structures are needed for the core algorithm. The solution can be implemented using:

• Simple node traversal with value comparisons
• No hash maps, queues, or other auxiliary structures required

The simplicity of the BST structure allows us to avoid complex helper data structures and instead rely on the inherent ordering properties of the tree for optimal performance.

5. Algorithm Walkthrough

Let's trace through the algorithm with a concrete example:

Input BST:

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

Query: LCA of nodes 2 and 8

Step 1: Start at root (value 6)

• Target nodes: 2 and 8
• Current node value: 6
• Since 2 < 6 and 8 > 6, nodes 2 and 8 are on different sides of the root
• Therefore, root (6) is their LCA

Step 2: Let's try a more complex example - LCA of nodes 2 and 4

• Start at root (value 6)
• Since both 2 and 4 are less than 6, move to left subtree
• Current node: 2
• Since 2 = 2 and 4 > 2, nodes are on different sides of node 2
• Therefore, node 2 is their LCA

Step 3: For nodes 3 and 5 in same subtree

• Start at root (value 6)
• Since both 3 and 5 are less than 6, move to left subtree
• Current node: 2
• Since both 3 and 5 are greater than 2, move to right subtree of node 2
• Current node: 4
• Since 3 < 4 and 5 < 4, move to left subtree of node 4
• Current node: 3
• Since 3 = 3 and 5 > 3, nodes are on different sides of node 3
• Therefore, node 3 is their LCA

The algorithm correctly handles all cases by leveraging BST property: for any node, all values in left subtree are smaller and all values in right subtree are larger. When we find a node where the two target values are on different sides, that node is their lowest common ancestor.

The key insight is that we can eliminate entire subtrees at each step, making the search efficient and avoiding unnecessary traversal.

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 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null, return null
        if (root == null) {
            return null;
        }
        
        // If both p and q are smaller than root, LCA must be in left subtree
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        
        // If both p and q are greater than root, LCA must be in right subtree
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        
        // If one value is smaller and other is greater than root,
        // or if root is equal to either p or q, then root is LCA
        return root;
    }
}

This solution leverages the BST property where for any node, all values in left subtree are smaller and all values in right subtree are greater. The algorithm recursively navigates toward the LCA by comparing node values with the current root, making it efficient and clean.

7. Complexity Analysis

Time Complexity: O(h) where h is the height of the BST. In the worst case (skewed tree), h = n, making it O(n). In a balanced BST, h = O(log n).

The algorithm traverses the tree from root to LCA by making one decision at each level - either go left or right. At each step, we perform O(1) operations (comparisons and pointer movements). Since we visit at most h nodes, the time complexity is O(h).

Space Complexity: O(1) for iterative solution or O(h) for recursive due to call stack.

The iterative approach uses only constant extra space for variables like current node, p, and q. The recursive solution requires O(h) space on the call stack in the worst case, as it may need to store a function call for each level of the tree.

Why these bounds are correct:

The solution is optimal because:

1. We must examine at least the path from root to LCA, which requires visiting O(h) nodes
2. Each node visit involves constant work - no redundant operations
3. The BST property allows us to eliminate half the search space at each step, achieving logarithmic performance in balanced trees

The bounds are tight because:

• In worst case (skewed tree), we must traverse all n nodes → O(n)
• In best case (balanced tree), we only need to traverse log n nodes → O(log n)

This complexity matches the theoretical lower bound for BST operations, making it near-optimal for this problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty BST: If root is null, LCA is undefined. The solution should handle this gracefully.
• Single node: If the BST has only one node, that node is its own LCA for any query.
• One node missing: If one of the target nodes doesn't exist in the tree, the result should be null or handled appropriately.

Duplicate Values and Repeated States

• Duplicate values in BST: In a valid BST, duplicates are typically not allowed (only in "BST with duplicates" variants). If duplicates exist, the algorithm must handle them correctly based on the problem's definition.
• Same node as both targets: If p and q are the same node, the LCA is that node itself.

Boundary Conditions

• Target nodes at extremes: When one or both target nodes are the minimum or maximum values in the tree, ensure traversal logic handles them correctly.
• Root node as LCA: When one target is the root and the other is in a subtree, the root is the LCA.

Common Implementation Mistakes

• Incorrect BST property checks: Forgetting to check if both nodes are in the same subtree (e.g., both less than root) or incorrectly comparing values.
• Mutating input: Modifying the tree structure or node values during traversal (though this is not required for LCA).
• Not handling null nodes: Failing to check for null inputs or null node references.
• Off-by-one errors in comparisons: Using <= instead of <, or vice versa, leading to incorrect traversal direction.

// Example edge case handling:
if (root == null || p == null || q == null) {
    return null;
}
if (p.val == q.val) {
    return p; // Same node
}

9. Alternative Approaches

There are several alternative approaches to finding the lowest common ancestor (LCA) in a BST, each with different trade-offs:

1. Post-order traversal with path tracking: Instead of leveraging BST properties, we can traverse the tree and maintain paths to both target nodes. When we find both nodes, we compare their paths to determine the LCA. This approach has O(n) time complexity in worst case and O(h) space for storing paths, where h is the height of the tree. It's less efficient than our optimized solution but works for general binary trees.

2. Parent pointer approach: If each node had a parent pointer, we could traverse upward from both nodes to find their intersection point. This would require O(h) time and space for storing visited ancestors, but it's more flexible for general trees.

3. Binary search approach: We could treat the BST as a sorted array and use binary search to find the LCA, but this requires converting the tree structure into an array representation which adds unnecessary overhead.

4. Iterative approach with stack: We can simulate the recursive solution using an explicit stack, but this adds complexity without improving performance.

The key advantage of our chosen approach is that it directly exploits the BST property (left subtree contains values less than root, right subtree contains values greater) to eliminate half of the search space at each step. This makes it optimal for BSTs with O(h) time complexity, where h is the height of the tree. The alternative approaches either lose this efficiency or add unnecessary complexity for a problem that has a clean, optimal solution using BST properties.

Our approach is superior because it's both time and space optimal for the specific constraint of a BST, while alternatives either don't leverage the BST structure or add unnecessary overhead.

10. Test Cases

// Test case 1: Basic case with valid LCA
// Input: BST with nodes 6, 2, 8, 0, 4, 7, 9, 3, 5
// Find LCA of nodes 2 and 8
// Expected: 6

// Test case 2: LCA is one of the nodes
// Input: BST with nodes 6, 2, 8, 0, 4, 7, 9, 3, 5
// Find LCA of nodes 2 and 4
// Expected: 2

// Test case 3: One node is ancestor of another
// Input: BST with nodes 6, 2, 8, 0, 4, 7, 9, 3, 5
// Find LCA of nodes 2 and 3
// Expected: 2

// Test case 4: Empty tree
// Input: null root
// Find LCA of nodes 1 and 2
// Expected: null

// Test case 5: Single node tree
// Input: BST with single node 1
// Find LCA of nodes 1 and 1
// Expected: 1

// Test case 6: Boundary values
// Input: BST with nodes 1, 2, 3, 4, 5
// Find LCA of nodes 1 and 5
// Expected: 1

// Test case 7: Duplicate values (if allowed)
// Input: BST with nodes 2, 1, 3, 2, 4 (with duplicate handling)
// Find LCA of nodes 2 and 4
// Expected: 2

Representative Sample Cases:

1. Basic case: BST with nodes [6,2,8,0,4,7,9,3,5], LCA of 2 and 8 → Expected: 6
2. Node as LCA: BST with nodes [6,2,8,0,4,7,9,3,5], LCA of 2 and 4 → Expected: 2
3. One node is ancestor: BST with nodes [6,2,8,0,4,7,9,3,5], LCA of 2 and 3 → Expected: 2

Tricky Case:

Duplicate handling: BST with nodes [2,1,3,2,4], LCA of 2 and 4 → Expected: 2 (if duplicates are handled by left subtree insertion)

Boundary Case:

Empty tree: null root, LCA of 1 and 2 → Expected: null

These test cases cover the essential scenarios including edge conditions, boundary values, and special cases that might break a naive implementation. The test suite should validate both the correctness of the algorithm and its handling of edge conditions like null inputs, single nodes, and boundary value scenarios.

11. Final Summary

The core idea is to leverage the BST property that for any node, all values in the left subtree are smaller and all values in the right subtree are larger than the node's value. By comparing the values of the two target nodes with the current node's value, we can determine which direction to traverse in the tree. This approach works because we're guaranteed that once we find a node where one target is in the left subtree and the other is in the right subtree (or one of them equals the current node), that node must be the lowest common ancestor.

The solution is efficient because it uses the BST's ordering property to eliminate half of the remaining search space at each step, achieving O(h) time complexity where h is the height of the tree. This is optimal for BST operations, and the space complexity is O(1) when using iterative approach or O(h) for recursive due to call stack.

What makes this solution particularly elegant is that it's a direct application of the BST ordering property, making it both intuitive and highly performant for the specific constraints of a binary search tree.