Problem Description

You are given a binary search tree (BST) and two nodes p and q that exist in the tree. Your task is to find the lowest common ancestor (LCA) of these two nodes.

The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants. Note that a node can be considered a descendant of itself, meaning if one of the nodes p or q is an ancestor of the other, then that ancestor node itself would be the LCA.

In a BST, recall that:

• All values in the left subtree of a node are less than the node's value
• All values in the right subtree of a node are greater than the node's value
• This property holds for every node in the tree

For example, if you have a BST and nodes p and q:

• If both p and q values are smaller than the current node's value, their LCA must be in the left subtree
• If both p and q values are larger than the current node's value, their LCA must be in the right subtree
• If one value is smaller and one is larger than the current node (or one equals the current node), then the current node is the LCA

The solution leverages the BST property to efficiently find the LCA by comparing the values of p and q with the current node and deciding which direction to traverse, avoiding the need to search the entire tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A tree is a special type of graph (specifically, a connected acyclic graph). The BST in this problem has nodes connected by edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a Binary Search Tree (BST), which is a tree data structure.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart leads us to use Depth-First Search (DFS).

Conclusion: The flowchart suggests using a DFS approach for finding the Lowest Common Ancestor in a Binary Search Tree.

Additional Context: While the flowchart correctly identifies DFS as the pattern, the actual solution leverages the BST property to optimize the traversal. Instead of exploring all paths, we can make intelligent decisions at each node:

• If both p and q values are less than the current node's value, we traverse left
• If both p and q values are greater than the current node's value, we traverse right
• Otherwise, we've found the LCA

This is essentially a modified DFS where the BST property guides our traversal direction, making it more efficient than a standard DFS that would explore all branches.

Intuition

The key insight comes from understanding the BST property: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger.

Let's think about where the LCA could be located. If we're standing at any node in the tree, there are only three possibilities for nodes p and q:

1. Both p and q are in the left subtree (both values < current node's value)
2. Both p and q are in the right subtree (both values > current node's value)
3. p and q are split across different subtrees, or one of them is the current node itself

The magic happens when we realize that in case 3, the current node MUST be the LCA! Why? Because if p and q are on different sides of the current node (or one equals the current node), then the current node is the first point where the paths from the root to p and to q diverge - which is exactly the definition of the lowest common ancestor.

This observation leads to a simple strategy: start at the root and keep moving towards the subtree that contains both nodes. The moment we find a node where p and q would go in different directions (or we're at p or q itself), we've found our LCA.

The beauty of this approach is that we don't need to search the entire tree or even keep track of paths. We can make a decision at each node based solely on comparing values: if current.val < min(p.val, q.val), go right; if current.val > max(p.val, q.val), go left; otherwise, we've found the LCA.

This turns what could be a complex tree traversal problem into a simple value comparison problem, taking advantage of the ordered nature of the BST.

Solution Approach

The implementation uses an iterative approach to traverse the BST, making decisions at each node based on value comparisons.

Algorithm Steps:

1. Start with root as the current node
2. Enter an infinite loop that continues until we find the LCA
3. At each iteration, compare the current node's value with both p.val and q.val:
   • If root.val < min(p.val, q.val): Both nodes are in the right subtree, so move to root.right
   • If root.val > max(p.val, q.val): Both nodes are in the left subtree, so move to root.left
   • Otherwise: We've found the LCA, return root

Key Implementation Details:

The solution uses a while 1 (infinite loop) structure that only exits when we return the LCA. This is guaranteed to terminate because:

• We're given that both p and q exist in the tree
• Each iteration moves us closer to the LCA
• The condition in the else clause will eventually be met

Why This Works:

When root.val is between p.val and q.val (inclusive), or equals one of them, we know that:

• If we go left, we'll lose access to the larger-valued node
• If we go right, we'll lose access to the smaller-valued node
• Therefore, the current node is the lowest point that can reach both nodes

Time and Space Complexity:

• Time Complexity: O(h) where h is the height of the tree. In the worst case (skewed tree), this could be O(n), but for a balanced BST, it's O(log n).
• Space Complexity: O(1) as we only use a constant amount of extra space (just moving the root pointer).

The iterative approach avoids the recursive call stack, making it more memory-efficient than a recursive solution while maintaining the same time complexity.

Example Walkthrough

Let's walk through finding the LCA of nodes with values 2 and 8 in this BST:

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

Step-by-step execution:

1. Start at root (6)
   • p.val = 2, q.val = 8
   • Check: Is 6 < both 2 and 8? No (6 is not less than 2)
   • Check: Is 6 > both 2 and 8? No (6 is not greater than 8)
   • Since 6 is between 2 and 8, node 6 is the LCA
   • Return node 6

Let's try another example with nodes 2 and 4:

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

1. Start at root (6)

   • p.val = 2, q.val = 4
   • Check: Is 6 > both 2 and 4? Yes!
   • Move to left child: root = root.left (node 2)

2. Current node (2)

   • Check: Is 2 < both 2 and 4? No (2 equals 2)
   • Check: Is 2 > both 2 and 4? No (2 is not greater than 4)
   • Since one node equals the current node, node 2 is the LCA
   • Return node 2

One more example with nodes 3 and 5:

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

1. Start at root (6)

   • p.val = 3, q.val = 5
   • Check: Is 6 > both 3 and 5? Yes!
   • Move to left child: root = root.left (node 2)

2. Current node (2)

   • Check: Is 2 < both 3 and 5? Yes!
   • Move to right child: root = root.right (node 4)

3. Current node (4)

   • Check: Is 4 < both 3 and 5? No (4 is between 3 and 5)
   • Check: Is 4 > both 3 and 5? No (4 is between 3 and 5)
   • Since 4 is between 3 and 5, node 4 is the LCA
   • Return node 4

The algorithm efficiently navigates down the tree, making exactly the right turns based on value comparisons, never needing to backtrack or search multiple paths.

Solution Implementation

Time and Space Complexity

The time complexity is O(h) where h is the height of the binary search tree. In the worst case when the tree is skewed (essentially a linked list), h = n where n is the number of nodes, making the time complexity O(n). In the best case of a balanced BST, the time complexity would be O(log n).

The space complexity is O(1) as the algorithm uses only a constant amount of extra space. The iterative approach with a while loop traverses the tree by updating the root pointer without using recursion or any additional data structures, requiring only a fixed amount of memory regardless of the input size.

Common Pitfalls

1. Incorrect Direction Logic

One of the most common mistakes is reversing the traversal direction logic. When both values are smaller than the current node, developers often incorrectly move left instead of right.

Incorrect Implementation:

if root.val < min(p.val, q.val):
    root = root.left  # Wrong! Should go right
elif root.val > max(p.val, q.val):
    root = root.right  # Wrong! Should go left

Why This Happens: The confusion arises from thinking about where the values are located rather than where we need to move. If root.val < min(p.val, q.val), both p and q have larger values than root, so they must be in the right subtree.

Correct Implementation:

if root.val < min(p.val, q.val):
    root = root.right  # Both nodes are greater, go right
elif root.val > max(p.val, q.val):
    root = root.left   # Both nodes are smaller, go left

2. Not Handling Edge Cases with Node Values

Another pitfall is not properly handling the case where one of the target nodes IS the LCA itself. Some implementations try to exclude equality checks.

Problematic Approach:

if p.val < root.val and q.val < root.val:
    root = root.left
elif p.val > root.val and q.val > root.val:
    root = root.right
else:
    return root

This works but using min() and max() with inclusive comparisons is cleaner and handles all cases including when p.val == root.val or q.val == root.val.

3. Assuming p.val < q.val

Don't assume any ordering between p and q values. The solution should work regardless of whether p's value is smaller or larger than q's value. Using min() and max() ensures the logic works for both cases.

Memory Tip: Think of it as "chasing" both nodes - if the current value is too small for both targets, move toward larger values (right); if too large for both, move toward smaller values (left).