#32 · Trees

Lowest Common Ancestor of a BST

Given a binary SEARCH tree and two of its nodes p and q, find their lowest common ancestor: the deepest node that has both p and q as descendants (a node counts as a descendant of itself).

MediumLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary search tree (BST)

For every node, all values in its left subtree are smaller and all values in its right subtree are larger. That ordering lets you decide at each node which single child can contain a given value, so lookups follow one root-to-node path.

Memory layout

Pointer-linked nodes. A path from the root has length h (the height): about log n if balanced, n if degenerate.

Operation	Cost
search one value	O(h)
find the LCA using the ordering	O(h) time, O(1) extra space (iterative)

Lowest common ancestor and the "split point"

In a BST the LCA of p and q is the first node, walking down from the root, whose value lies between them (inclusive). Above it, both targets are on the same side; at it, they split (or one equals it).

Memory layout

No extra structures: one node pointer and two integers.

Operation	Cost
walk to the split point	O(h)

Why it fits

Ordering turns a search of the whole tree (O(n)) into a single downward walk (O(h)): at each node exactly one of "go left", "go right", "stop" is correct.
The first node with lo ≤ value ≤ hi is automatically the lowest one, because we descend only while both targets are on the same side.
Nothing needs to be stored: no paths, no recursion stack, so the iterative version is O(1) space.

Why alternatives degrade

General binary-tree LCA (search both subtrees):: Correct for any tree but visits up to every node: O(n) time and O(h) stack, ignoring the ordering that makes this problem easy.
Store parent pointers, then climb:: Needs an extra O(n) map or modified nodes, and climbing from both nodes costs O(h) anyway.
Compare inorder positions:: Inorder positions tell order, not ancestry; you would still need the paths.

Four approaches, from naive to production

1 · beginner

Compare the two root-to-node paths

time O(h)space O(h)

Record the path from the root to p and the path from the root to q. The LCA is the last node the two paths share.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    auto pathTo = [&](TreeNode* target) {
        vector<TreeNode*> path;
        TreeNode* node = root;
        while (node) {
            path.push_back(node);
            if (target->val < node->val) node = node->left;
            else if (target->val > node->val) node = node->right;
            else break;
        }
        return path;
    };
    vector<TreeNode*> a = pathTo(p);
    vector<TreeNode*> b = pathTo(q);
    TreeNode* lca = root;
    for (size_t i = 0; i < min(a.size(), b.size()) && a[i] == b[i]; i++) lca = a[i];
    return lca;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> a = pathTo(root, p);
    List<TreeNode> b = pathTo(root, q);
    TreeNode lca = root;
    for (int i = 0; i < Math.min(a.size(), b.size()) && a.get(i) == b.get(i); i++) lca = a.get(i);
    return lca;
}

private List<TreeNode> pathTo(TreeNode root, TreeNode target) {
    List<TreeNode> path = new ArrayList<>();
    TreeNode node = root;
    while (node != null) {
        path.add(node);
        if (target.val < node.val) node = node.left;
        else if (target.val > node.val) node = node.right;
        else break;
    }
    return path;
}

def lowest_common_ancestor(root, p, q):
    def path_to(target):
        path = []
        node = root
        while node:
            path.append(node)
            if target.val < node.val: node = node.left
            elif target.val > node.val: node = node.right
            else: break
        return path
    a = path_to(p)
    b = path_to(q)
    lca = root
    i = 0
    while i < min(len(a), len(b)) and a[i] is b[i]:
        lca = a[i]
        i += 1
    return lca

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  const pathTo = (target: TreeNode): TreeNode[] => {
    const path: TreeNode[] = [];
    let node = root;
    while (node) {
      path.push(node);
      if (target.val < node.val) node = node.left;
      else if (target.val > node.val) node = node.right;
      else break;
    }
    return path;
  };
  const a = pathTo(p);
  const b = pathTo(q);
  let lca = root;
  for (let i = 0; i < Math.min(a.length, b.length) && a[i] === b[i]; i++) lca = a[i];
  return lca;
}

Flaws & bottlenecks

Stores two paths of up to h nodes each, when none of that has to be remembered.
Walks the common prefix of the two paths twice.
Needs an extra pass to compare the paths.

Interviewer cross-questions

Is the answer always on both paths?

Say: Yes: an ancestor of both nodes lies on both root-to-node paths. The lowest one is the last shared node of the two paths, because after it the paths diverge.

What if p is an ancestor of q?

Say: Then the path to p is a prefix of the path to q, and the last shared node is p itself, which is correct since a node counts as its own descendant.

How do you avoid storing the paths?

Say: Walk once: keep going down while both targets are on the same side of the current node. The first node where they split is the answer.

2 · intermediate

Generic recursion (works for any binary tree)

time O(n)space O(h)

Search both subtrees. If p or q is found, return it up. A node that receives a result from BOTH sides is the LCA; otherwise pass up whichever side found something.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q: return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right: return root
    return left or right

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

Flaws & bottlenecks

Ignores the BST ordering, so it may visit every node (O(n)) where O(h) is enough.
Recursion depth is the height of the tree.
Relies on both targets actually existing in the tree.

Interviewer cross-questions

When is this the right solution?

Say: For a general binary tree (no ordering), where nothing better is possible without extra structure. It is the standard answer for "Lowest Common Ancestor of a Binary Tree".

Why can it return as soon as it meets p or q?

Say: If the other target is below that node, the node itself is the answer. If it is elsewhere, the caller will combine the result with the other side. Either way going deeper is unnecessary.

What if q is not in the tree at all?

Say: The code would return p as the answer (it never learns that q is missing). You would need to verify existence, for example with counters, to return nothing.

3 · advanced

BST recursion

time O(h)space O(h)

If both values are smaller than the current node, the answer is in the left subtree; if both are larger, it is in the right subtree; otherwise the current node is the split point and is the answer.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
    if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
    return root;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
    if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
    return root;
}

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

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
  if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
  return root;
}

Flaws & bottlenecks

Uses O(h) call-stack space even though the recursion is a tail call (many languages do not optimize it).
Assumes p and q are in the tree and that the tree is a valid BST.
A skewed tree makes h = n.

Interviewer cross-questions

Why is the node where they split the LCA?

Say: Above it the targets share the same side, so every ancestor so far is a common ancestor but not the lowest. At the split node one target is on each side (or one equals the node), so no child is a common ancestor: it is the lowest.

What if p or q equals the current node?

Say: Then neither "both smaller" nor "both larger" holds, so the node is returned: a node is its own descendant, so this is correct.

What is the complexity on a balanced tree?

Say: O(log n): one downward path. On a degenerate tree (a chain) it is O(n).

4 · expert

Iterative with a [lo, hi] window

time O(h)space O(1)

Compute lo = min(p, q) and hi = max(p, q) once. Walk down: go right while the node is below lo, left while it is above hi, and return the first node inside [lo, hi].

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    int lo = min(p->val, q->val);
    int hi = max(p->val, q->val);
    TreeNode* node = root;
    while (node) {
        if (node->val < lo) node = node->right;
        else if (node->val > hi) node = node->left;
        else return node;
    }
    return nullptr;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    int lo = Math.min(p.val, q.val);
    int hi = Math.max(p.val, q.val);
    TreeNode node = root;
    while (node != null) {
        if (node.val < lo) node = node.right;
        else if (node.val > hi) node = node.left;
        else return node;
    }
    return null;
}

def lowest_common_ancestor(root, p, q):
    lo = min(p.val, q.val)
    hi = max(p.val, q.val)
    node = root
    while node:
        if node.val < lo: node = node.right
        elif node.val > hi: node = node.left
        else: return node
    return None

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

Flaws & bottlenecks

Assumes both targets exist and the tree is a valid BST; it returns a wrong node (the closest value) otherwise.
Values must be comparable with < and > (no duplicates in a BST).
Returns nothing only if the tree is empty.

Interviewer cross-questions

Why is there no need for a stack?

Say: We never go back up: the decision at each node is final (one direction or stop), so a single pointer is the entire state. This turns O(h) space into O(1).

Why compute lo and hi up front?

Say: It removes the "which one is smaller" logic from the loop and makes the stopping rule a single range test. It also avoids repeated min/max work at every node.

How would you validate the inputs in production?

Say: Check that both values exist in the tree first (two O(h) lookups) so a missing value produces an error instead of a plausible but wrong node.

Synchronized code walkthrough

Showing: Compare the two root-to-node paths — shares the player above; click any step to jump.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    auto pathTo = [&](TreeNode* target) {
        vector<TreeNode*> path;
        TreeNode* node = root;
        while (node) {
            path.push_back(node);
            if (target->val < node->val) node = node->left;
            else if (target->val > node->val) node = node->right;
            else break;
        }
        return path;
    };
    vector<TreeNode*> a = pathTo(p);
    vector<TreeNode*> b = pathTo(q);
    TreeNode* lca = root;
    for (size_t i = 0; i < min(a.size(), b.size()) && a[i] == b[i]; i++) lca = a[i];
    return lca;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> a = pathTo(root, p);
    List<TreeNode> b = pathTo(root, q);
    TreeNode lca = root;
    for (int i = 0; i < Math.min(a.size(), b.size()) && a.get(i) == b.get(i); i++) lca = a.get(i);
    return lca;
}

private List<TreeNode> pathTo(TreeNode root, TreeNode target) {
    List<TreeNode> path = new ArrayList<>();
    TreeNode node = root;
    while (node != null) {
        path.add(node);
        if (target.val < node.val) node = node.left;
        else if (target.val > node.val) node = node.right;
        else break;
    }
    return path;
}

def lowest_common_ancestor(root, p, q):
    def path_to(target):
        path = []
        node = root
        while node:
            path.append(node)
            if target.val < node.val: node = node.left
            elif target.val > node.val: node = node.right
            else: break
        return path
    a = path_to(p)
    b = path_to(q)
    lca = root
    i = 0
    while i < min(len(a), len(b)) and a[i] is b[i]:
        lca = a[i]
        i += 1
    return lca

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  const pathTo = (target: TreeNode): TreeNode[] => {
    const path: TreeNode[] = [];
    let node = root;
    while (node) {
      path.push(node);
      if (target.val < node.val) node = node.left;
      else if (target.val > node.val) node = node.right;
      else break;
    }
    return path;
  };
  const a = pathTo(p);
  const b = pathTo(q);
  let lca = root;
  for (let i = 0; i < Math.min(a.length, b.length) && a[i] === b[i]; i++) lca = a[i];
  return lca;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q: return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right: return root
    return left or right

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
    if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
    return root;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
    if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
    return root;
}

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

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
  if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
  return root;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    int lo = min(p->val, q->val);
    int hi = max(p->val, q->val);
    TreeNode* node = root;
    while (node) {
        if (node->val < lo) node = node->right;
        else if (node->val > hi) node = node->left;
        else return node;
    }
    return nullptr;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    int lo = Math.min(p.val, q.val);
    int hi = Math.max(p.val, q.val);
    TreeNode node = root;
    while (node != null) {
        if (node.val < lo) node = node.right;
        else if (node.val > hi) node = node.left;
        else return node;
    }
    return null;
}

def lowest_common_ancestor(root, p, q):
    lo = min(p.val, q.val)
    hi = max(p.val, q.val)
    node = root
    while node:
        if node.val < lo: node = node.right
        elif node.val > hi: node = node.left
        else: return node
    return None

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