Lowest Common Ancestor of a Binary Search Tree

Problem

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

The lowest common ancestor is defined 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).

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.

Constraints:

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.

Solution

Approach: Leverage BST Property

The key insight is to use the BST property: if both nodes are less than current, go left; if both are greater, go right; otherwise, current is the LCA.

Implementation

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            # Both nodes are in left subtree
            if p.val < root.val and q.val < root.val:
                root = root.left
            # Both nodes are in right subtree
            elif p.val > root.val and q.val > root.val:
                root = root.right
            # Found the split point
            else:
                return root

Recursive Version:

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

Complexity Analysis

Time Complexity: O(h), where h is the height of the tree. We traverse from root towards leaves.
Space Complexity: O(1) for iterative, O(h) for recursive.

Key Insights

BST Property: In a BST, all values in the left subtree are less than the node, and all in the right are greater.
Split Point: The LCA is the first node where p and q are on different sides (or one equals the node).
No Need to Search Both Subtrees: Unlike in a regular binary tree, we know which direction to go based on values.
Node Can Be Its Own Ancestor: If one node is the ancestor of the other, that node is the LCA.
Guaranteed to Find: Since both p and q exist in the tree, we’re guaranteed to find an LCA.