Lowest Common Ancestor of a Binary Search Tree

Ishaan S Published 24 Oct, 2026

You are given the root of a binary search tree (every value in a node's left subtree is smaller than the node, every value in its right subtree is larger) and two different nodes p and q that both belong to the tree.

Return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as part of its own subtree, so if p is an ancestor of q, the answer is p itself.

Trees are written in level order: the root first, then each level from left to right, with null marking a missing child. For example [4,2,null,1] is a root 4 whose left child 2 has a left child 1.

In the examples p and q are written as values; your function receives the actual nodes with those values, and the judge checks the value of the node you return.

Example 1

Input: root = [20,10,30,5,15,25,35], p = 5, q = 15 Output: 10 Why: 5 is in the left subtree of 10 and 15 is in its right subtree, so 10 is where their paths split.

Example 2

Input: root = [20,10,30,5,15,25,35], p = 15, q = 25 Output: 20 Why: 15 lies left of the root 20 and 25 lies right of it, so the root is the answer.

Example 3

Input: root = [20,10,30,5,15,25,35], p = 10, q = 5 Output: 10 Why: 5 is a child of 10, and a node is its own ancestor, so 10 is the answer.

Constraints

2 <= number of nodes <= 10⁴
-10⁹ <= Node.val <= 10⁹
All values are distinct, and the tree is a valid binary search tree.
p != q, and both are nodes of the tree.

Pattern Path · Binary Search Trees · problem 99 of 169

Start at the root. Using only the values, can you tell which side of the tree p and q are on?

If both values are smaller than the current node, both nodes live in the left subtree, so the answer is there too. The same holds on the right for larger values.

Walk down from the root. The first node where p and q are not on the same side (or where one of them is the current node) is the answer.

Target: O(h) time, O(1) extra space.

Start simple

Record the root-to-node path for p and for q (ignoring the ordering), then return the last node the two paths share: O(n) time and O(n) space.

The key idea

The ordering of a binary search tree tells you, at every node, which subtree a value must be in. Use it to follow the path from the root toward both targets at once.

If p and q are both smaller than the current node, both are in the left subtree, so their lowest common ancestor is too: move left.
If both are larger, move right for the same reason.
Otherwise the paths split here: one target is on the left and the other on the right, or the current node is one of them. No deeper node can contain both, while this node does, so it is the answer.

This never examines more than one root-to-leaf path, so it runs in time proportional to the tree's height: O(log n) for a balanced tree and O(n) in the worst case. Written as a loop it needs only constant extra space. A general binary tree has no ordering to guide you, which is why this version is easier than the general one.

Complexity

Time: O(h)
Space: O(1)

Python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        node = root
        while node:
            if p.val < node.val and q.val < node.val:
                node = node.left    # both targets are in the left subtree
            elif p.val > node.val and q.val > node.val:
                node = node.right   # both targets are in the right subtree
            else:
                return node         # the targets split here, or one of them is this node
        return None

JavaScript

var lowestCommonAncestor = function(root, p, q) {
  let node = root;
  while (node) {
    if (p.val < node.val && q.val < node.val) {
      node = node.left;   // both targets are in the left subtree
    } else if (p.val > node.val && q.val > node.val) {
      node = node.right;  // both targets are in the right subtree
    } else {
      return node;        // the targets split here, or one of them is this node
    }
  }
  return null;
};

What the interviewer is checking

The interviewer checks whether you exploit the BST ordering to walk a single path instead of using the general tree algorithm, and whether you handle the case where one node is the ancestor of the other.

Mistakes to avoid

Ignoring the BST property and searching both subtrees like in a general tree, which works but misses the point.
Forgetting that a node can be its own ancestor, and continuing past p when q is below it.
Comparing nodes instead of their values, or assuming p.val is smaller than q.val.

Follow-ups to expect

What if the tree is an ordinary binary tree? (Post-order search returning found nodes.)
What if p or q might be missing from the tree? (Verify both exist first.)
What if nodes have parent pointers? (Intersect the two upward paths.)

In real software

Finding the narrowest common range covering two keys in an ordered index, or the most specific shared category in a sorted hierarchy, follows the same split-point walk.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}

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

public class Main {
    // Builds a tree from a level-order array where null marks a missing child.
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < a.length) {
            TreeNode n = q.poll();
            if (i < a.length && a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            i++;
            if (i < a.length && a[i] != null) { n.right = new TreeNode(a[i]); q.add(n.right); }
            i++;
        }
        return root;
    }

static TreeNode find(TreeNode node, int val) {
        while (node != null && node.val != val) node = val < node.val ? node.left : node.right;
        return node;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{20, 10, 30, 5, 15, 25, 35});
        TreeNode ans = new Solution().lowestCommonAncestor(root, find(root, 5), find(root, 15));
        System.out.println(ans == null ? null : ans.val); // 10
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return nullptr;
    }
};

// Builds a tree from a level-order list where NIL marks a missing child.
const int NIL = INT_MIN;
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == NIL) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front(); q.pop();
        if (i < a.size() && a[i] != NIL) { n->left = new TreeNode(a[i]); q.push(n->left); }
        i++;
        if (i < a.size() && a[i] != NIL) { n->right = new TreeNode(a[i]); q.push(n->right); }
        i++;
    }
    return root;
}

TreeNode* find(TreeNode* node, int val) {
    while (node && node->val != val) node = val < node->val ? node->left : node->right;
    return node;
}

int main() {
    TreeNode* root = build({20, 10, 30, 5, 15, 25, 35});
    TreeNode* ans = Solution().lowestCommonAncestor(root, find(root, 5), find(root, 15));
    if (ans) cout << ans->val << endl;  // 10
    else cout << "null" << endl;
}

Topics #099 #t-bst Binary Search Tree DFS Medium Practice Tree