Lowest Common Ancestor of a BST

The Lowest Common Ancestor (LCA) problem in a Binary Search Tree requires finding the deepest node that is an ancestor of two given nodes. This solution leverages BST properties to achieve optimal O(log n) time complexity through iterative traversal.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that both nodes p and q exist in the BST?
2. Can we assume that p and q are distinct nodes, or could they be the same node?
3. What is the expected time complexity for the solution? Should we aim for O(log n) or O(n)?
4. Is it acceptable to modify the input BST during our solution?
5. What should we return if one or both nodes are not found in the tree?

Restated problem: Given a Binary Search Tree (BST) and two nodes p and q, find their Lowest Common Ancestor (LCA). The LCA is 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 BST, and two TreeNode objects p and q
• Output: The TreeNode that represents the LCA of p and q

Constraints and assumptions:

• All node values are unique (as per typical BST definition)
• The BST property holds: for every node, all values in left subtree are less than the node's value, and all values in right subtree are greater
• Both p and q exist in the tree (we can assume they're valid nodes)
• We can modify the input structure if needed, but prefer immutable approach

Data shape and hidden structure: The problem leverages the BST property which provides a clear ordering relationship between nodes. This ordered structure allows us to make decisions about which direction to traverse without needing to explore the entire tree. The solution space is effectively reduced by using the BST's inherent ordering.

Core insight: Unlike a general binary tree where we'd need to search for both nodes and trace paths, in a BST we can leverage the ordering property to make directional decisions based on node values relative to p and q, making this problem significantly more efficient than the general case.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern is Binary Search Tree (BST) property exploitation combined with tree traversal optimization.

Why this problem fits that pattern

The problem explicitly mentions a BST, which provides a critical structural property: 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. This ordered property allows us to eliminate half of the search space at each step, making it a prime candidate for binary search optimization in tree structure.

Core insight needed to solve it

The key insight is that we don't need to find the path to each node and then compare paths. Instead, we can leverage the BST property: if both nodes are smaller than the current node, we search the left subtree; if both are larger, we search the right subtree. When one node is smaller and the other is larger than the current node, or when the current node equals one of the target nodes, we've found our LCA.

The problem signals this pattern through:

• "Lowest Common Ancestor" - a classic tree traversal problem
• "BST" - the ordered structure enables binary search-style optimization
• The constraint that we're looking for a single node that is the lowest (deepest) common ancestor

This is fundamentally different from finding LCA in a general binary tree where we'd need to build paths or use parent pointers, because BST structure provides deterministic navigation.

3. Approach Evolution

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 these paths to find their last common node. This would work but it's O(n²) in worst case because for each node we might have to traverse the entire tree to find its path. 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 make this much more efficient. Instead of storing paths, I can traverse the tree once and at each step make a decision based on the relative values of p and q compared to current node.

The key insight is that in a BST, if both p and q are smaller than current node, I go left. If both are larger, I go right. When one is smaller and one is larger (or one equals current node), then current node must be the LCA.

This approach reduces to O(h) where h is height of tree, which is O(log n) for balanced BST and O(n) for skewed tree. This is much better than the O(n²) brute force approach.

Let me trace through this logic more carefully:

• If both nodes are in left subtree, we can ignore right subtree entirely
• If both nodes are in right subtree, we can ignore left subtree entirely
• If nodes split across left and right subtrees (or one equals current), we found our LCA

The invariant I'm maintaining is that at each step, the current node represents a valid ancestor candidate, and we're narrowing down to the actual LCA by leveraging BST ordering.

This is a clean iterative solution that avoids storing paths and takes advantage of the BST structure directly.

4. Data Structure Choice

For the Lowest Common Ancestor (LCA) problem in a Binary Search Tree, I'll use the following data structures:

Primary Data Structures:

1. TreeNode class - This is the fundamental building block representing each node in the BST. Each node contains:

   • val: The integer value stored in the node
   • left: Reference to the left child node (smaller values)
   • right: Reference to the right child node (larger values)

2. Stack - Used in the iterative approach to simulate the recursive call stack, enabling us to traverse the tree without recursion.

Why Each Data Structure Is Needed:

The TreeNode class is essential because:

• It represents the actual BST structure with the key property that for any node, all values in the left subtree are smaller and all values in the right subtree are larger
• It provides the necessary navigation capability to move between parent and child nodes
• It allows us to leverage the BST property for efficient searching

The Stack is used in the iterative solution because:

• It enables us to traverse the BST without recursion, which can be beneficial for very deep trees where stack overflow might occur
• It maintains the path from root to current node, allowing us to track our traversal state
• It provides O(1) push/pop operations for maintaining the traversal stack

Time and Space Impact:

• TreeNode structure: O(1) space per node, O(n) total space for n nodes
• Stack usage: O(h) space where h is the height of the tree (O(log n) average case, O(n) worst case)
• Overall space complexity: O(h) for iterative approach, O(h) for recursive due to call stack

Helper Structure:

• No additional helper structures are needed beyond the basic TreeNode and Stack, as we can leverage the BST's inherent ordering property to guide our search without additional data structures.

The choice of these structures directly enables us to take advantage of the BST's ordering property, making our search for LCA highly efficient by eliminating entire subtrees at each step.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Consider this BST:

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

We want to find LCA of nodes 2 and 8.

Step 1: Start at root (6)

• Current node value = 6
• p = 2, q = 8
• Since 2 < 6 and 8 > 6, we have p < current and q > current
• This means p and q are on different sides of the current node, so 6 is their LCA

Step 2: Let's try another example - LCA of nodes 3 and 5

• Start at root (6)
• Current node value = 6
• p = 3, q = 5
• Since both 3 < 6 and 5 < 6, both nodes are in left subtree
• Move to left child (2)

Step 3: At node 2

• Current node value = 2
• p = 3, q = 5
• Since 3 > 2 and 5 > 2, both nodes are in right subtree of 2
• Move to right child (4)

Step 4: At node 4

• Current node value = 4
• p = 3, q = 5
• Since 3 < 4 and 5 > 4, p and q are on different sides of 4
• Therefore, 4 is their LCA

The algorithm handles edge cases naturally:

• If one node is the ancestor of another, we'll eventually find the ancestor as the split point
• If nodes are same, we return that node directly
• If one node is root and other is in subtree, root is returned

The key insight is that we can leverage BST properties to avoid full traversal - we only need to find the first node where p and q diverge into different subtrees.

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 the 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 the right subtree
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        
        // If p and q are on different sides of root,
        // or one of them equals root, then root is LCA
        return root;
    }
}

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 values with the current node, making it efficient and clean.

7. Complexity Analysis

Time Complexity: O(h) where h is the height of the BST, which translates to O(log n) for a balanced tree and O(n) for a skewed tree.

The algorithm traverses the tree from root to the LCA node, making one decision at each level based on the BST property. At each step, we perform O(1) comparisons to determine whether to go left or right. Since we visit at most one node per level, and there are at most h levels in the tree, the time complexity is O(h).

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

For the iterative approach, we only use a constant amount of extra space (pointers to nodes). For the recursive approach, in the worst case of a skewed tree, the call stack depth equals the height of the tree, resulting in O(h) space complexity.

Why these bounds are correct:

• The height h is the maximum number of edges from root to the deepest leaf, which bounds our traversal
• Each node is visited at most once in the path from root to LCA, so we don't have redundant operations
• The BST property allows us to eliminate half the search space at each step in a balanced tree, making it logarithmic

Optimality: This is optimal for the BST LCA problem because we must examine at least the path from root to the LCA to determine the answer. Any algorithm that finds LCA in a BST must traverse at least h nodes, making O(h) the best possible time complexity. The space complexity of O(1) for iterative solution is also optimal among approaches that don't use additional data structures.

8. Edge Cases & Pitfalls

The most common edge cases and pitfalls when implementing LCA in a BST include:

Empty Input Handling: If either node is null, the problem typically assumes we return null or throw an exception. The solution must explicitly handle these cases to avoid NullPointerExceptions.

Single Node Tree: When the tree has only one node, that node is its own LCA for any query involving it. The algorithm must correctly handle this base case.

Duplicate Values: BSTs can have duplicate values, but the problem usually assumes unique values. If duplicates exist, the LCA logic must be carefully considered to ensure correct traversal behavior.

Node Not Found: If one or both nodes don't exist in the tree, the solution should handle this gracefully. Some implementations return null or throw an exception.

Query Nodes Are Same: When p and q refer to the same node, the LCA is simply that node itself. This case must be handled early in the algorithm.

Boundary Conditions: When one node is the ancestor of another, the solution must correctly identify the deeper node as the LCA.

Implementation Pitfalls:

• Using == instead of .equals() for node value comparison in Java
• Not properly maintaining BST property during traversal (e.g., going left when we should go right)
• Incorrectly assuming that if one node is smaller than root and another is larger, the root must be LCA (this only works for distinct nodes)
• Failing to handle null checks in recursive approaches
• Not considering that the LCA might be one of the input nodes itself

These edge cases highlight why careful input validation and boundary condition handling are crucial for a robust solution.

9. Alternative Approaches

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

1. Post-order Traversal with Path Tracking Instead of leveraging BST properties, we can perform a post-order traversal to find paths from root to both nodes, then compare these paths to find the last common node. This approach works for any binary tree but loses the BST optimization benefits.

2. Parent Pointer Approach If each node had a parent pointer, we could traverse upward from both nodes to find their intersection point. This approach requires modifying the tree structure and adds O(n) space complexity for storing parent references.

3. Iterative Binary Search Tree Traversal We can simulate the BST search process iteratively, moving toward the nodes while tracking the last valid ancestor. This is essentially the same as our solution but with explicit loop management instead of recursion.

4. Recursive with Full Tree Traversal A recursive approach that traverses the entire tree and returns the LCA node, checking if both target nodes exist in each subtree. This is O(n) time and space complexity without leveraging BST properties.

The main advantage of our chosen solution is that it takes full advantage of the BST property to achieve O(h) time complexity where h is the height, while alternatives either lose this efficiency or require additional space for parent pointers or path tracking.

Our approach is optimal for BSTs because it directly exploits the ordering property that makes this problem solvable in logarithmic time, whereas alternatives either require full tree traversal or additional data structures.

10. Test Cases

// Test case 1: Basic valid case
// Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
// Expected: 6
// Tree structure:
//       6
//      / \
//     2   8
//    / \ / \
//   0  4 7 9
//     / \
//    3   5

// Test case 2: One node is ancestor of another
// Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
// Expected: 2
// Node 2 is LCA of node 2 and node 4

// Test case 3: Edge case - single node
// Input: root = [1], p = 1, q = 1
// Expected: 1

// Test case 4: Edge case - empty tree (should not occur per problem constraints)
// Input: root = null, p = 1, q = 2
// Expected: null (but problem guarantees valid inputs)

// Test case 5: Values at boundaries
// Input: root = [2,1,3], p = 1, q = 3
// Expected: 2

// Test case 6: Duplicate values (if allowed)
// Input: root = [2,1,2], p = 1, q = 2
// Expected: 2

// Test case 7: Values not in tree (should not occur per problem constraints)
// Input: root = [2,1,3], p = 5, q = 6
// Expected: null (but problem guarantees valid inputs)

The test cases cover:

• Basic BST structure with valid LCA
• One node being ancestor of another
• Edge case of single node tree
• Boundary conditions with extreme values
• Duplicate value handling
• Invalid input scenarios (though problem constraints guarantee valid inputs)

These cases ensure the solution handles all expected BST traversal patterns and edge conditions properly.

11. Final Summary

The core insight is that in a BST, we can leverage the ordered property to efficiently navigate toward the LCA by comparing node values with the target values, eliminating half of the tree at each step. This approach is optimal because it takes advantage of the BST's inherent structure to achieve O(h) time complexity where h is the height of the tree, and O(1) space complexity. The solution works by iteratively moving down the tree from the root, choosing the left or right child based on whether both target values are smaller or larger than the current node's value, effectively narrowing our search space until we find the first node that lies between the two target values.