Problem Statement

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 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).

Link To the Problem

Intuition

When both target nodes p and q lie on the same side of the current node (either both in the left or both in the right subtree), the Lowest Common Ancestor (LCA) must also be on that side.

However, when they diverge — one node is on the left and the other on the right (or one is equal to the current node) — the current node itself becomes their lowest common ancestor.

Approach

1. Start from the root node.

2. If both p and q have values smaller than root.val, the LCA must be in the left subtree, so recurse left.

3. If both p and q have values greater than root.val, the LCA must be in the right subtree, so recurse right.

4. If the values diverge (i.e., one on each side, or one equals the root), then the current root is the LCA.

This logic works because of the Binary Search Tree (BST) property — left subtree values < root < right subtree values.

Complexity

• Time complexity: O(h), where h is where is the height of the tree.
  • In a balanced BST, h=log(n),
  • In the worst case (skewed tree), h=n
• Space complexity:
  • Recursive approach: O(h) due to the recursion stack, where h is the height of the tree.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base case: if the tree is empty
        if not root:
            return None

        # If both p and q are smaller, LCA is in the left subtree
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        # If both p and q are greater, LCA is in the right subtree
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        # Otherwise, root is the split point — the LCA
        else:
            return root