Skip to main content

235 - Lowest Common Ancestor of a Binary Search Tree

Difficulty: Medium | Pattern: BST Property | Company tags: Amazon, Facebook, LinkedIn

Problem Statement​

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

The LCA is defined as the lowest node in the tree that has both p and q as descendants (a node can 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

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2  (2 is an ancestor of 4)

Approach: Exploit BST Property — O(h), O(1)​

Key insight: In a BST, if both p and q are less than root, the LCA is in the left subtree. If both are greater, it's in the right subtree. Otherwise, root is the LCA (they split here, or one of them is the root).

def lowestCommonAncestor(root, p, q):
    while root:
        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
    return None

Algorithm Flow​

Recursive Version​

def lowestCommonAncestor(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    return root

Dry Run​

BST: [6,2,8,0,4,7,9], p=2, q=4

  • root=6: p.val=2 lt 6 AND q.val=4 lt 6 → go left
  • root=2: p.val=2 not lt 2 (equal) → else branch → return 2

LCA = 2 ✓ (2 is an ancestor of 4, and it IS p)

p=2, q=8:

  • root=6: 2 lt 6 but 8 gt 6 → else → return 6 ✓

Comparison with LC 236 (General Binary Tree LCA)​

LC 235 BSTLC 236 Binary Tree
Uses BST propertyYesNo
TimeO(h)O(n)
SpaceO(1) iterativeO(h)

The BST solution is simpler because we can navigate directly using value comparisons.

Complexity​

  • Time: O(h) — O(log n) balanced, O(n) worst case skewed
  • Space: O(1) iterative

Key Terms​

TermDefinition in this problem's context
BST ordering propertyFor every node, all left-subtree values are smaller and all right-subtree values are larger — this lets us decide direction using only value comparisons, no need to search both subtrees.
Split pointThe node where p and q diverge to different subtrees (or one equals the current node) — this is exactly the LCA.
Ancestor (self-inclusive)A node counts as its own ancestor, so if p is an ancestor of q, p itself is the LCA.
Iterative descentWalking down from root using a while loop instead of recursion, achieving O(1) space instead of O(h) call-stack space.

FAQ​

  1. Can this be solved without extra space? Yes — the iterative version uses O(1) space since it just reassigns root while descending; the recursive version uses O(h) stack space instead.

  2. What if p or q doesn't exist in the tree? The standard solution assumes both nodes exist in the tree (as per LeetCode's constraints); if that's not guaranteed, you'd first verify both nodes are present via a traversal before trusting the result.

  3. How would this change if it were a general binary tree instead of a BST? You could no longer use value comparisons to choose a direction; you'd need to search both subtrees recursively and combine results — this is exactly LC 236, which runs in O(n) instead of O(h).

  4. What's the follow-up interviewers usually ask? "What if the tree has parent pointers?" — you can then walk up from both nodes similar to finding the intersection point of two linked lists, or solve it without ever touching the root.

  5. Does this work correctly when p and q are the same node? Yes — the loop will keep descending toward that node until p.val == root.val (and thus q.val == root.val), triggering the else branch and returning that node.

Quick Revision​

  • Pattern: exploit BST ordering to navigate directly toward the LCA, no need to explore both subtrees.
  • If both p.val and q.val are less than root.val, LCA lies in the left subtree — move left.
  • If both are greater, LCA lies in the right subtree — move right.
  • Otherwise (values split across root, or one equals root), root is the LCA — stop and return it.
  • Iterative version: O(h) time, O(1) space — preferred for interviews.
  • Recursive version: same O(h) time, but O(h) stack space.
  • A node is considered its own ancestor, so if p is an ancestor of q, the answer is p.
  • Contrast with LC 236 (general binary tree): no ordering property, must search both subtrees, O(n) time, O(h) space.
  • h = O(log n) for a balanced BST, O(n) for a completely skewed one.