LeetEye LeetEye
Medium Tree Traversal ~5 min

Lowest Common Ancestor of a Binary Search Tree

trees 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 the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Examples

Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
LCA of 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
LCA of 2 and 4 is 2 (a node can be its own ancestor).
Key Insight

Use BST property: if both p and q are smaller, go left. If both are larger, go right. Otherwise, current node is the LCA.

BST LCA: if both smaller go left, if both larger go right, else current is LCA (split point or match).

How to Approach This Problem

Pattern Recognition: When you see keywords like lowest common ancestor of a binary search tree trees, think Tree Traversal.

Step-by-Step Reasoning

1 If p.val < root.val AND q.val < root.val:
Answer: LCA is in left subtree
Both nodes are smaller than root, so both are in the left subtree. LCA must be there.
2 If p.val > root.val AND q.val > root.val:
Answer: LCA is in right subtree
Both nodes are larger than root, so both are in the right subtree. LCA must be there.
3 If p.val < root.val AND q.val > root.val (or vice versa):
Answer: Root is the LCA
One in left subtree, one in right. Root is the deepest node containing both.
4 If p.val == root.val or q.val == root.val:
Answer: Root is the LCA
If one node IS the root, root is an ancestor of both (itself and the other). This is the LCA.
5 In a general binary tree, we can't use this approach because:
Answer: We can't determine which subtree contains a value
BST ordering tells us exactly where each value is. General trees require checking both subtrees.
6 The time complexity is:
Answer: O(h) where h is height
We traverse one path from root to LCA. In balanced BST, h = O(log n). In worst case (skewed), h = O(n).

Solution

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

Complexity Analysis

Time O(h)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Tree Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye