LCA of a BST

BST property — descend toward the split point

Use the BST property to decide which subtree to explore.

Published Apr 16, 2026

Problem

Given the root of a Binary Search Tree and two of its nodes p and q, return their lowest common ancestor (LCA) — the deepest node that has both p and q in its subtree.

Input

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

Output

Input

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

Output

Explanation

A node can be its own descendant — 2 is its own ancestor.

Intuition

A BST node is the LCA of p and q if and only if it lies between them in value (min(p, q) ≤ node ≤ max(p, q)). Why?

If both p and q are smaller than the current node, both live in the left subtree — descend left.
If both are larger, both live in the right subtree — descend right.
Otherwise the values straddle the current node, so this is the deepest node that contains both. Done.

The general-binary-tree LCA needs a search (#236). The BST version doesn't — values do the navigation for free.

Approach

Recursive descent

TimeO(h)

SpaceO(h)

Recommended

Walk down following the rule above. The first node whose value lies between p.val and q.val (inclusive) is the LCA.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let pv = p.as_ref().unwrap().borrow().val;
        let qv = q.as_ref().unwrap().borrow().val;
        let lo = pv.min(qv);
        let hi = pv.max(qv);
        fn walk(
            node: Option<Rc<RefCell<TreeNode>>>,
            lo: i32,
            hi: i32,
        ) -> Option<Rc<RefCell<TreeNode>>> {
            let n = node.clone()?;
            let v = n.borrow().val;
            if v < lo {
                walk(n.borrow().right.clone(), lo, hi)
            } else if v > hi {
                walk(n.borrow().left.clone(), lo, hi)
            } else {
                node
            }
        }
        walk(root, lo, hi)
    }
}

Rust · runnable

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  const lo = Math.min(p!.val, q!.val);
  const hi = Math.max(p!.val, q!.val);
  const walk = (n: TreeNode | null): TreeNode | null => {
    if (n === null) return null;
    if (n.val < lo) return walk(n.right);
    if (n.val > hi) return walk(n.left);
    return n;
  };
  return walk(root);
}

TypeScript · runnable

Iterative

TimeO(h)

SpaceO(1)

The recursion is tail-recursive — each call only returns whatever the next call returns. So we can rewrite as a while loop and drop the call stack to O(1) space.

This matters in practice: BST operations on a balanced tree of 2³⁰ keys still recurse 30 deep, which is fine for any stack — but for a skewed BST (sorted insertion), the recursion can blow the stack.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let pv = p.as_ref().unwrap().borrow().val;
        let qv = q.as_ref().unwrap().borrow().val;
        let lo = pv.min(qv);
        let hi = pv.max(qv);
        let mut curr = root;
        while let Some(n) = curr.clone() {
            let v = n.borrow().val;
            if v < lo {
                curr= n.borrow().right.clone();
            } else if v > hi {
                curr = n.borrow().left.clone();
            } else {
                return curr;
            }
        }
        None
    }
}

Rust · runnable

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  const lo = Math.min(p!.val, q!.val);
  const hi = Math.max(p!.val, q!.val);
  let curr = root;
  while (curr !== null) {
    if (curr.val < lo) curr = curr.right;
    else if (curr.val > hi) curr = curr.left;
    else return curr;
  }
  return null;
}

TypeScript · runnable

Trace

p = 2, q = 8 on the example BST:

step	curr.val	comparison	next
1	6	2 ≤ 6 ≤ 8	return 6

For p = 2, q = 4 (split happens lower):

step	curr.val	comparison	next
1	6	both 2 and 4 < 6	go left
2	2	2 ≤ 2 ≤ 4	return 2

Edge cases

One node is the ancestor of the other — covered by the inclusive lo ≤ v ≤ hi check; the ancestor itself is the LCA.
p == q — the algorithm returns that node.
Skewed BST — iterative version is O(1) space; recursive is O(n) stack.

Takeaway

BST problems usually beat the general-tree version because the values are the navigation. Search, insert, delete, range-count, range-sum, predecessor/successor, and LCA all leverage the same compare-and-descend skeleton. When you see a BST hint, the first question to ask is "what does the value tell me about which child to visit?"

Medium#230

Kth Smallest Element in a BST

In-order traversal gives sorted order. Can you do it iteratively with a stack?

Easy#104

Maximum Depth of Binary Tree

1 + max(left_depth, right_depth). This IS the recursive template.

Easy#226

Invert Binary Tree

The simplest recursive tree transformation. Swap left and right, recurse.