Lowest Common Ancestor of a Binary Search Tree

MediumTrees · Binary Search Tree🧩 Binary Search Tree & In-order LeetCode #235 ↗Updated Oct 30, 2026

Problem

You get the root of a binary search tree and two of its nodes, p and q. Return their lowest common ancestor: the deepest node that has both p and q in its subtree, where a node is allowed to be an ancestor of itself.

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

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

Inputroot = [2,1], p = 2, q = 1Output2

2 ≤ nodes ≤ 10⁵ · -10⁹ ≤ Node.val ≤ 10⁹ · all values distinct · p ≠ q, both are in the tree

Try it yourself

Java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

In a BST, both targets sit on the same side of a node as long as the node is smaller (or larger) than both. The first node whose value lies between p and q (inclusive) is where their search paths split — that node is the LCA.

PatternBinary Search Tree & In-order

Instinct The tree is a BST? Its in-order walk is a sorted list and every node splits the search space - think "sorted array in tree form", not "visit everything".

Memory hack Left is less, right is more, in-order reads the sorted score - and every node lives inside a (low, high) fence set by its ancestors.

Open the Binary Search Tree & In-order guide →

Approaches

Brute ForceGeneric Root-to-Node Paths

Time O(n)Space O(n)

Ignore the ordering and treat it as any binary tree: a DFS with backtracking records the root-to-node path for p and for q. The LCA is the last node the two paths have in common.

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> pathP = new ArrayList<>(), pathQ = new ArrayList<>();
    findPath(root, p, pathP);
    findPath(root, q, pathQ);
    TreeNode lca = null;
    for (int i = 0; i < Math.min(pathP.size(), pathQ.size()); i++) {
        if (pathP.get(i) != pathQ.get(i)) break;
        lca = pathP.get(i); // still on the shared prefix
    }
    return lca;
}
private boolean findPath(TreeNode node, TreeNode target, List<TreeNode> path) {
    if (node == null) return false;
    path.add(node);
    if (node == target) return true;
    if (findPath(node.left, target, path) || findPath(node.right, target, path)) return true;
    path.remove(path.size() - 1); // backtrack: target is not below this node
    return false;
}

Works on any binary tree, but explores the whole tree and wastes the BST property.

BetterBST Search Paths

Time O(h)Space O(h)

Use the ordering to find each target like a normal BST search, collecting the visited nodes. Each path has length at most h, and the deepest node they share is again the answer.

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> pathP = searchPath(root, p.val);
    List<TreeNode> pathQ = searchPath(root, q.val);
    TreeNode lca = root;
    for (int i = 0; i < Math.min(pathP.size(), pathQ.size()); i++) {
        if (pathP.get(i) != pathQ.get(i)) break;
        lca = pathP.get(i);
    }
    return lca;
}
private List<TreeNode> searchPath(TreeNode node, int target) {
    List<TreeNode> path = new ArrayList<>();
    while (node != null) {
        path.add(node);
        if (target == node.val) break;
        node = target < node.val ? node.left : node.right;
    }
    return path;
}

Only touches two root-to-node paths, but still stores them.

OptimalWalk Down to the Split Point

Time O(h)Space O(1)

Start at the root. If both values are smaller, the LCA must be in the left subtree; if both are larger, it must be in the right subtree. Otherwise the targets split here (or one of them is this node), so this node is the LCA. The two paths are followed together without storing them.

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode node = root;
    while (node != null) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;   // both targets on the left
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;  // both targets on the right
        } else {
            return node;        // paths split here (or node is p or q)
        }
    }
    return null;
}

Single downward walk, constant memory — the expected answer.

Pro tip

Compare values, not nodes, and keep it iterative — a skewed tree of 10⁵ nodes can overflow a recursive version.

At a glance

Level	Approach	Time	Space
Brute Force	Generic Root-to-Node Paths	`O(n)`	`O(n)`
Better	BST Search Paths	`O(h)`	`O(h)`
Optimal	Walk Down to the Split Point	`O(h)`	`O(1)`

Common pitfalls

Forgetting a node can be its own ancestor — when p is above q, p is the answer.
Computing (node.val - p.val) * (node.val - q.val) — overflows with values up to 10⁹.
Using the general binary-tree LCA and never mentioning the BST shortcut.

Interview tips

Draw the tree and show where the two search paths diverge — that picture is the proof.
Contrast with LCA of a general binary tree (236), which needs a full DFS.
Mention h = log n for a balanced BST but h = n for a skewed one.

Pattern

BST guided descent → when an ordered tree lets each comparison discard a whole subtree.

My notes saved in this browser