Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Additional information

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

Example 1:

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8

Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4

Output: 2

Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2, 1], p = 2, q = 1

Output: 2

Recursive DFS (Leveraging BST Property)

Intuition

A Binary Search Tree (BST) has a strict property: all nodes in the left subtree are smaller than the root, and all nodes in the right subtree are greater than the root.

We can use this to our advantage to find the Lowest Common Ancestor.

1. If both p and q are strictly smaller than the current node, the LCA must be in the left subtree.
2. If both p and q are strictly greater than the current node, the LCA must be in the right subtree.
3. If one is smaller and the other is greater (or if one of them equals the current node), a "split" occurs. The current node is the highest point where they share the same path, meaning it is the Lowest Common Ancestor.

Algorithm

1. Start at the root node.
2. Check if both p.val and q.val are greater than root.val. If so, recursively call the function on root.right.
3. Check if both p.val and q.val are less than root.val. If so, recursively call the function on root.left.
4. If neither of the above conditions is met, we have found the split point (or matched p or q). Return root.

def lowest_common_ancestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor(root.right, p, q)
    elif p.val < root.val and q.val < root.val:
        return lowest_common_ancestor(root.left, p, q)
    else:
        return root

Time & Space Complexity

• Time complexity: O(h)

• Reason: We traverse down the height h of the BST. In the worst case (skewed tree), this is O(n). In a balanced tree, it is O(log n).

• Space complexity: O(h)

• Reason: The recursion stack consumes memory proportional to the height of the tree.

Iterative Traversal (Optimal Space)

Intuition

Since we don't need to backtrack up the tree, we don't actually need recursion. We can optimize the space complexity by using a simple while loop to traverse down the tree.

We maintain a curr pointer starting at the root. We update curr to curr.left or curr.right depending on the values of p and q until we find the split point.

Algorithm

1. Initialize a pointer curr = root.
2. Loop while curr is not None:

• If p.val > curr.val and q.val > curr.val, move curr = curr.right.
• Else if p.val < curr.val and q.val < curr.val, move curr = curr.left.
• Else, return curr (split point found).

def lowest_common_ancestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    curr = root
    
    while curr:
        if p.val > curr.val and q.val > curr.val:
            curr = curr.right
        elif p.val < curr.val and q.val < curr.val:
            curr = curr.left
        else:
            return curr

Time & Space Complexity

• Time complexity: O(h)

• Reason: We only visit one node per level, down to a maximum of h levels.

• Space complexity: O(1)

• Reason: We only use a single curr pointer, eliminating the recursion stack overhead.