What is the brute force approach and complexity for Lowest Common Ancestor of a BST?

Record the path from the root to p and to q; the last node both paths share is the answer with time complexity O(H) and space complexity O(H).

What is the optimal approach and complexity for Lowest Common Ancestor of a BST?

Use the BST order: go left if both are smaller, right if both are larger, else this node is the answer with optimal time complexity O(H) and space complexity O(1).

How do you identify the pattern for Lowest Common Ancestor of a BST?

Look for key signals in the prompt: "lowest common ancestor" indicates We want the first node that splits the two targets. Walk down from the top. Do not check the whole tree.; "binary search tree" indicates Values are ordered, so one comparison rules out a whole side for each target.; "a node can be its own ancestor" indicates If the walk stops on one of the targets, that target is the answer. The stop rule must handle equal values..

Lowest Common Ancestor of a BST

Medium·LeetCode #235Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree DFS — LCA on a BST (top-down walk)

Complexity:O(H)→O(H)

Key Insight

Start at the root. If both p and q are smaller than the node, both live in its left subtree, so move left. If both are larger, move right. Otherwise the two targets are on different sides (or one of them is this node), so this node is the answer.

Core Validity Invariant

A node is the answer when p and q are not both smaller and not both larger than it. Then one target is on each side, or the node is one of them.

Problem

You are given the root of a binary search tree (BST) and two nodes p and q that are both in the tree.

Find their lowest common ancestor (LCA). This is the lowest node that has both p and q below it. A node counts as its own ancestor, so if p is above q, the answer is p.

Return the node itself, not its value.

Input

root, the root of a BST (it has at least 2 nodes), and two different node pointers p and q.

Output

The node that is the lowest common ancestor of p and q.

Example 1

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

Output: 6

2 is in the left subtree of 6 and 8 is in the right subtree, so 6 is the first node that splits them.

Example 2

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

Output: 2

4 is below 2. A node counts as its own ancestor, so the answer is 2 itself.

Example 3

Input: root = [2, 1], p = 2, q = 1

Output: 2

1 is the left child of 2, so 2 is the answer.

Constraints

• The number of nodes in the tree is in the range [2, 10^5].
• −10^9 ≤ Node.val ≤ 10^9
• All Node.val are unique.
• p ≠ q
• p and q will exist in the BST.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
This tree is a BST. At any node, which side holds the smaller values and which side holds the larger ones?
2.
If both targets are smaller than the current node, can either of them be in the right subtree?
3.
What does it mean when the two targets are on different sides of the current node?
4.
Can the answer be one of the two targets? What would the walk look like then?
5.
Do I need to visit both subtrees? How many nodes do I visit in the worst case?

Brute force approach

Idea

Find the path from the root down to p, and the path from the root down to q. Both paths start at the root, so walk them together. The last node they share is the lowest common ancestor. In a BST, each path is found by the normal search in O(H) steps, so the brute is correct, but it keeps two whole paths in memory.

Thinking process

1
The LCA is on the path from the root to p and on the path from the root to q. It is the last node the two paths share.
2
In a BST we can build the path to p without any search: go left if p is smaller than the node, right if it is larger.
3
Example: root 6, p = 3, q = 5. The path to 3 is 6, 2, 4, 3. The path to 5 is 6, 2, 4, 5.
4
Walk the two lists together: 6 = 6, 2 = 2, 4 = 4, then 3 ≠ 5. The last shared node is 4.
5
If p is above q, the path to p is the start of the path to q. The walk stops at the end of p's path, and p is the last shared node.

Code & Implementation

brute.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
    // Path from the root down to target. The BST search picks the side by value.
    vector<TreeNode*> pathTo(TreeNode* root, TreeNode* target) {
        vector<TreeNode*> path;
        for (TreeNode* cur = root; cur; ) {
            path.push_back(cur);
            if (cur == target) break;
            cur = target->val < cur->val ? cur->left : cur->right;
        }
        return path;
    }

public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> a = pathTo(root, p);
        vector<TreeNode*> b = pathTo(root, q);
        // Both paths start at the root. The last node they share is the answer.
        TreeNode* lca = nullptr;
        for (size_t i = 0; i < a.size() && i < b.size() && a[i] == b[i]; i++) lca = a[i];
        return lca;
    }
};

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode 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 {
    // Path from the root down to target. The BST search picks the side by value.
    private List<TreeNode> pathTo(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<>();
        for (TreeNode cur = root; cur != null; ) {
            path.add(cur);
            if (cur == target) break;
            cur = target.val < cur.val ? cur.left : cur.right;
        }
        return path;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> a = pathTo(root, p);
        List<TreeNode> b = pathTo(root, q);
        // Both paths start at the root. The last node they share is the answer.
        TreeNode lca = null;
        for (int i = 0; i < a.size() && i < b.size() && a.get(i) == b.get(i); i++) {
            lca = a.get(i);
        }
        return lca;
    }
}

from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Path from the root down to target. The BST search picks the side by value.
        def pathTo(node: Optional[TreeNode], target: TreeNode) -> List[TreeNode]:
            path: List[TreeNode] = []
            cur = node
            while cur:
                path.append(cur)
                if cur == target:
                    break
                cur = cur.left if target.val < cur.val else cur.right
            return path

        a = pathTo(root, p)
        b = pathTo(root, q)
        # Both paths start at the root. The last node they share is the answer.
        lca = None
        for x, y in zip(a, b):
            if x == y:
                lca = x
            else:
                break
        return lca  # type: ignore

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

export function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (!root || !p || !q) return null;

    // Path from the root down to target. The BST search picks the side by value.
    function pathTo(node: TreeNode | null, target: TreeNode): TreeNode[] {
        const path: TreeNode[] = [];
        for (let cur: TreeNode | null = node; cur !== null; ) {
            path.push(cur);
            if (cur === target) break;
            cur = target.val < cur.val ? cur.left : cur.right;
        }
        return path;
    }

    const a = pathTo(root, p);
    const b = pathTo(root, q);
    // Both paths start at the root. The last node they share is the answer.
    let lca: TreeNode | null = null;
    for (let i = 0; i < a.length && i < b.length && a[i] === b[i]; i++) {
        lca = a[i];
    }
    return lca;
}

Complexity

Time O(H)Space O(H)

Time is also O(H), the same as the optimal. The difference is memory: the brute stores two whole paths of up to H nodes each. The optimal makes the same walk with one pointer and stores nothing, so it uses O(1) space.

Optimized approach

Idea

Start from brute force

The brute force builds two full paths and then compares them. The optimal never builds a path. It makes one decision per node, and it stops at the split.

Find the repeated work

The brute force stores the whole path to p and the whole path to q. Everything above the split is shared, and everything below it is never needed. The BST order already says which way to go, so the stored paths are wasted work.

Define the state — what variables do I need?

cur: The node we are standing on. It starts at the root and moves down one level per step.
p and q: The two targets. We only compare their values with cur.val.

Define validity

A node is the answer when p and q are not both smaller and not both larger than it. Then one target is on each side, or the node is one of them.

Define the transitions — when does each pointer move, and why is it safe?

Both p and q are smaller than cur

cur = cur->left

A BST keeps all smaller values on the left. Neither target can be on the right or be cur itself.

Both p and q are larger than cur

cur = cur->right

The same rule on the right side.

Anything else

return cur

The targets split here, or one of them is cur. Either way, cur is the lowest node that has both of them below it or is one of them.

What does the current window add to the answer?

Each step either rules out one whole subtree or returns the answer. There is no running total to keep.

Code & Implementation

optimal.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* cur = root;
        while (cur) {
            if (p->val < cur->val && q->val < cur->val) cur = cur->left;        // both in the left subtree
            else if (p->val > cur->val && q->val > cur->val) cur = cur->right;  // both in the right subtree
            else return cur;  // split here, or cur is p or q itself
        }
        return nullptr;
    }
};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode 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) {
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val && q.val < cur.val) cur = cur.left;        // both in the left subtree
            else if (p.val > cur.val && q.val > cur.val) cur = cur.right;  // both in the right subtree
            else return cur;  // split here, or cur is p or q itself
        }
        return null;
    }
}

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cur = root
        while cur:
            if p.val < cur.val and q.val < cur.val:
                cur = cur.left        # both in the left subtree
            elif p.val > cur.val and q.val > cur.val:
                cur = cur.right       # both in the right subtree
            else:
                return cur            # split here, or cur is p or q itself
        return None  # type: ignore

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

export function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (!p || !q) return null;
    let cur = root;
    while (cur) {
        if (p.val < cur.val && q.val < cur.val) cur = cur.left;        // both in the left subtree
        else if (p.val > cur.val && q.val > cur.val) cur = cur.right;  // both in the right subtree
        else return cur;  // split here, or cur is p or q itself
    }
    return null;
}

Complexity

Time O(H)Space O(1)

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Record the path from the root to p and to q; the last node both paths share is the answer	O(H)	O(H)
Optimal	Use the BST order: go left if both are smaller, right if both are larger, else this node is the answer	O(H)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“lowest common ancestor”We want the first node that splits the two targets. Walk down from the top. Do not check the whole tree.
“binary search tree”Values are ordered, so one comparison rules out a whole side for each target.
“a node can be its own ancestor”If the walk stops on one of the targets, that target is the answer. The stop rule must handle equal values.

Ordered tree (BST)+two targets+first node where they split+one path down → O(H)→Tree DFS — LCA on a BST (top-down walk)

The BST order tells us which side each target is on, so every step drops one whole subtree. This is the anchor of the LCA sub-pattern: compare both targets with the node, then go left, go right, or stop. Only one comparison per level is needed, not a search of both sides. LC 236 has no order, so it has to check both sides, which is the next question.

Don't make this mistake

Using <= in the split check

✗ if (p->val <= cur->val && q->val <= cur->val) cur = cur->left;

✓ if (p->val < cur->val && q->val < cur->val) cur = cur->left;

Equal values need the strict test. On the tree above with p = 2 and q = 0: at 6 both are smaller, so we go to 2. At 2, p equals the node, so <= says both are smaller and the walk goes left to 0, which returns 0. The right answer is 2, because 2 is an ancestor of 0 and counts as its own ancestor.

Returning the end of p's path (a node can be its own ancestor)

✗ return pathToP.back();

✓ return the last node that both paths share

Take p = 4 and q = 2. The path to 4 is 6, 2, 4, and the path to 2 is 6, 2. The end of p's path is 4. But 2 is an ancestor of 4, and a node counts as its own ancestor, so the answer is 2. Only the shared part of the two paths can decide the answer.

Pattern confusion: searching both subtrees like LC 236

The BST order makes one side impossible, so searching both subtrees is wasted work. The answer is still correct, but on the tree above with p = 3 and q = 5, a full search visits all 9 nodes. The BST walk visits only 3 of them: 6, 2 and 4.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture