Data Structures
powered by pagefind esc close · ↑↓ navigate · ↵ open
practice · easy · from Binary Search Trees

Lowest Common Ancestor in a BST

time
O(h)
space
O(1)
tags
bst · recursion

in the wild Find the most specific shared category of two products in a taxonomy tree, or the closest junction joining two waypoints in a routing tree.

Problem

Given the root of a BST and two values p and q known to exist in it, return the lowest common ancestor (LCA) node — the deepest node that has both p and q in its subtree. A node may be its own ancestor.

Examples

        6
       / \
      2   8
     / \ / \
    0  4 7  9
       / \
      3   5

  LCA(2, 8) = 6       (split happens at the root)
  LCA(2, 4) = 2       (2 is an ancestor of 4)
  LCA(3, 5) = 4
  LCA(0, 5) = 2

Why this is the canonical "exploit the BST ordering" problem

In a generic binary tree, finding LCA is O(n): you walk both subtrees and merge information up. In a BST, the ordering turns it into O(h):

You walk a single root-to-LCA path. No backtracking, no auxiliary structure, no second pass. The BST property lets you "feel" where the split happens just by comparing.

This is the cleanest example of a theme that runs through every BST algorithm: "the ordering is your map — don't waste it". The same idea lets BST insert/search/min/max all be O(h), versus O(n) on an unordered binary tree.

Hints

Hint 1 — when must the LCA be the current node?

The LCA is the first (highest-up) node that separates p and q into different subtrees. If both p and q are on the same side of the current node, you can safely descend that side without losing the LCA.

Hint 2 — the split test, written tightly

Let lo = min(p, q) and hi = max(p, q). The LCA is the first node whose value lies in [lo, hi] — anything strictly less goes right; strictly greater goes left.

Hint 3 — iterate, no recursion needed

The recursion is tail-recursive — you only descend, never combine. A simple while loop with node = node.left / node = node.right is cleaner and uses O(1) extra space.

Solution

from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    left:  Optional["Node"] = None
    right: Optional["Node"] = None

def lca_bst(root: Optional[Node], p: int, q: int) -> Optional[Node]:
    lo, hi = min(p, q), max(p, q)
    n = root
    while n is not None:
        if   n.val < lo: n = n.right     # both descendants are larger
        elif n.val > hi: n = n.left      # both descendants are smaller
        else:            return n        # the split — this is the LCA
    return None

# Build the example tree.
root = Node(6,
            Node(2, Node(0), Node(4, Node(3), Node(5))),
            Node(8, Node(7), Node(9)))
cases = [(2, 8, 6), (2, 4, 2), (3, 5, 4), (0, 5, 2)]
for p, q, expected in cases:
    got  = lca_bst(root, p, q).val
    mark = "✓" if got == expected else "✗"
    print(f"{mark} lca_bst(.., {p}, {q}) = {got}  (expected {expected})")
class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

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

const root = new Node(6,
  new Node(2, new Node(0), new Node(4, new Node(3), new Node(5))),
  new Node(8, new Node(7), new Node(9)));
const cases = [[2, 8, 6], [2, 4, 2], [3, 5, 4], [0, 5, 2]];
for (const [p, q, expected] of cases) {
  const got = lcaBst(root, p, q).val;
  console.log(`${got === expected ? "✓" : "✗"} lcaBst(.., ${p}, ${q}) = ${got}  (expected ${expected})`);
}
pub struct Node {
    pub val:   i32,
    pub left:  Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

pub fn lca_bst<'a>(root: &'a Option<Box<Node>>, p: i32, q: i32) -> Option<&'a Node> {
    let (lo, hi) = (p.min(q), p.max(q));
    let mut cur  = root.as_deref();
    while let Some(n) = cur {
        if      n.val < lo { cur = n.right.as_deref(); }
        else if n.val > hi { cur = n.left.as_deref();  }
        else               { return Some(n); }
    }
    None
}

fn leaf(v: i32) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: None, right: None }))
}
fn node(v: i32, l: Option<Box<Node>>, r: Option<Box<Node>>) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: l, right: r }))
}

fn main() {
    let root = node(6,
        node(2, leaf(0), node(4, leaf(3), leaf(5))),
        node(8, leaf(7), leaf(9)));
    let cases = [(2, 8, 6), (2, 4, 2), (3, 5, 4), (0, 5, 2)];
    for (p, q, expected) in cases {
        let got  = lca_bst(&root, p, q).unwrap().val;
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} lca_bst(.., {}, {}) = {}  (expected {})", p, q, got, expected);
    }
}
#include <algorithm>
#include <iostream>

struct Node {
    int   val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

Node* lca_bst(Node* root, int p, int q) {
    int lo = std::min(p, q), hi = std::max(p, q);
    Node* n = root;
    while (n) {
        if      (n->val < lo) n = n->right;
        else if (n->val > hi) n = n->left;
        else                   return n;
    }
    return nullptr;
}

int main() {
    Node* root = new Node(6,
        new Node(2, new Node(0), new Node(4, new Node(3), new Node(5))),
        new Node(8, new Node(7), new Node(9)));
    int cases[][3] = { {2, 8, 6}, {2, 4, 2}, {3, 5, 4}, {0, 5, 2} };
    for (auto& c : cases) {
        int got = lca_bst(root, c[0], c[1])->val;
        std::cout << (got == c[2] ? "✓" : "✗")
                  << " lca_bst(.., " << c[0] << ", " << c[1] << ") = " << got
                  << "  (expected " << c[2] << ")\n";
    }
}
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int          val;
    struct Node* left;
    struct Node* right;
} Node;

static int imin(int a, int b) { return a < b ? a : b; }
static int imax(int a, int b) { return a > b ? a : b; }

Node* lca_bst(Node* root, int p, int q) {
    int lo = imin(p, q), hi = imax(p, q);
    Node* n = root;
    while (n) {
        if      (n->val < lo) n = n->right;
        else if (n->val > hi) n = n->left;
        else                   return n;
    }
    return NULL;
}

static Node* mk(int v, Node* l, Node* r) {
    Node* n = malloc(sizeof(Node));
    n->val = v; n->left = l; n->right = r;
    return n;
}

int main(void) {
    Node* root = mk(6,
        mk(2, mk(0, NULL, NULL), mk(4, mk(3, NULL, NULL), mk(5, NULL, NULL))),
        mk(8, mk(7, NULL, NULL), mk(9, NULL, NULL)));
    int cases[][3] = { {2, 8, 6}, {2, 4, 2}, {3, 5, 4}, {0, 5, 2} };
    for (int i = 0; i < 4; i++) {
        int got = lca_bst(root, cases[i][0], cases[i][1])->val;
        printf("%s lca_bst(.., %d, %d) = %d  (expected %d)\n",
               got == cases[i][2] ? "✓" : "✗",
               cases[i][0], cases[i][1], got, cases[i][2]);
    }
    return 0;
}

The whole problem collapses to "walk down until you straddle the values". Notice how every implementation is essentially the same six lines.

Complexity

Time
O(h) — one root-to-LCA descent. In a balanced BST that's O(log n); in a degenerate one, O(n).
Space
O(1) — iterative version uses no stack. The recursive version uses O(h) stack.
vs general tree LCA
Without the BST ordering, you need an O(n) post-order pass (or pre-process with O(n) Euler tour + RMQ for O(1) per query). The BST gives O(log n) per query, no preprocessing.

In the wild

Variations