LeetCode 235: Lowest Common Ancestor in a Binary Search Tree — Find the First Split Point

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode and also presented on NeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode, NeetCode, and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original problem pages.

Article Summary

Given two nodes in a binary search tree, we need to find their lowest common ancestor: the deepest node that is an ancestor of both nodes.

A general binary-tree solution may search multiple branches. A binary search tree gives us additional ordering information:

• Values in the left subtree are smaller than the current node.
• Values in the right subtree are larger than the current node.

Therefore, we can determine whether both target nodes are on the same side of the current node. The first node where their search paths split—or where the current node equals one of the targets—is their lowest common ancestor.

The iterative solution runs in O(h) time and uses O(1) auxiliary space, where h is the height of the tree.

Original Problem and Credit

This article is based on the LeetCode problem “Lowest Common Ancestor of a Binary Search Tree” and the corresponding NeetCode practice page.

• Original LeetCode problem: LeetCode 235 — Lowest Common Ancestor of a Binary Search Tree
• NeetCode practice page: Lowest Common Ancestor in Binary Search Tree
• Platforms: LeetCode and NeetCode
• Original problem, examples, and constraints credit: LeetCode and NeetCode
• Explanation, adaptation, analysis, and commentary: Andy

Original Problem in Simple Terms

We are given:

• The root of a binary search tree.
• A node p.
• A different node q.

Both p and q exist in the tree, and every node has a unique value.

We must return the lowest node in the tree that contains both p and q in its subtree. A node is allowed to be an ancestor of itself.

For example, when p is already an ancestor of q, the answer can be p.

Important Constraints

• The tree contains between 2 and 100 nodes.
• Each node value is between -100 and 100.
• All node values are unique because the input is a binary search tree.
• p and q are different nodes.
• Both target nodes exist in the tree.

Real-World Scenario

Imagine a hypothetical authorization platform that organizes policy rules in a binary search tree according to their unique numeric IDs.

Each policy rule can have more specific rules beneath it:

• Smaller rule IDs are stored in the left subtree.
• Larger rule IDs are stored in the right subtree.

Two services use policy rules p and q. The platform needs to locate the most specific policy scope that contains both rules.

That shared policy scope is equivalent to the lowest common ancestor of p and q.

Suppose the current policy has ID 5:

• If both requested rule IDs are smaller than 5, their shared scope must be somewhere in the left subtree.
• If both are larger than 5, their shared scope must be somewhere in the right subtree.
• If one is smaller and the other is larger, their paths separate at policy 5, so policy 5 is their lowest shared scope.
• If the current policy is one of the requested policies, it is also the lowest shared scope because a node can be its own ancestor.

This scenario is hypothetical, but it preserves the exact structure and rules of the original computational problem.

Examples

Example 1: The Nodes Are in Different Subtrees

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

Output:
5

Node 3 is smaller than 5, while node 8 is larger than 5. Their paths split at node 5, so 5 is their lowest common ancestor.

Example 2: One Target Is an Ancestor of the Other

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

Output:
3

Node 3 is one of the target nodes, and node 4 is in its subtree. Because a node can be an ancestor of itself, node 3 is the lowest common ancestor.

Edge Example: Both Nodes Are in the Same Subtree

Consider the same tree with:

p = 7
q = 9

Both values are greater than 5, so we move to node 8. At node 8, one target is smaller and the other is larger. Therefore, node 8 is their lowest common ancestor.

Mapping to the Original Problem

The adaptation changes only the terminology. The tree structure, ordering rules, inputs, outputs, and algorithm remain unchanged.

Solution Intuition

1. Start with the Binary Search Tree Property

In a binary search tree, every node divides the remaining values into two groups:

• All values in the left subtree are smaller.
• All values in the right subtree are larger.

This means that the current node tells us where both targets must be located.

2. Compare Both Targets with the Current Node

At each node, there are three meaningful situations.

Both Targets Are Smaller

If:

p->val < current->val
and
q->val < current->val

then both targets are in the left subtree.

The current node cannot be the lowest common ancestor because a deeper common ancestor may exist on the left. We continue with current->left.

Both Targets Are Larger

If:

p->val > current->val
and
q->val > current->val

then both targets are in the right subtree.

We continue with current->right.

The Targets Split—or the Current Node Is a Target

In every other case:

• One target is smaller and the other is larger, or
• The current node equals p, or
• The current node equals q.

The current node is therefore the first point where the target paths no longer continue together. It is the lowest common ancestor.

3. Why We Do Not Need a Full Tree Traversal

A general binary tree does not tell us which branch contains a target, so we may need to search both sides.

A binary search tree provides enough ordering information to eliminate one entire subtree at each step. We only follow a single path from the root toward the answer.

This is similar to ordinary binary-search-tree lookup.

Algorithm

1. Set current to root.
2. While current is not nullptr:
   1. If both p and q have values smaller than current->val, move to current->left.
   2. Otherwise, if both values are larger than current->val, move to current->right.
   3. Otherwise, return current.
3. Return nullptr only as a defensive fallback.

Under the problem constraints, the defensive fallback should not be reached because both target nodes exist in the tree.

Why the Algorithm Works

We maintain the following invariant:

At the beginning of every iteration, the lowest common ancestor of p and q is inside the subtree rooted at current.

Initially, current is the root, so the invariant is true because the root's subtree contains the entire tree.

If both target values are smaller than current->val, the binary search tree property guarantees that both targets are in the left subtree. Their lowest common ancestor must also be in that subtree, so moving left preserves the invariant.

Similarly, if both target values are larger, both nodes and their lowest common ancestor must be in the right subtree. Moving right preserves the invariant.

Otherwise, the targets do not both belong to the same child subtree:

• Their paths split at current, or
• current is itself one of the targets.

In either case, current is a common ancestor. Any descendant of current can belong to at most one of the two relevant directions, so no lower node can be an ancestor of both targets. Therefore, current is the lowest common ancestor.

Thus, the algorithm returns the correct node.

Complexity Analysis

Let h be the height of the binary search tree.

Time Complexity

O(h)

The algorithm follows one downward path through the tree. At each visited node, it performs a constant number of comparisons.

• In a balanced binary search tree, h = O(log n), so the running time is O(log n).
• In a completely skewed binary search tree, h = O(n), so the worst-case running time is O(n).

Here, n is the number of nodes in the tree.

Space Complexity

O(1)

The iterative solution stores only a pointer to the current node. It does not use a recursion stack or another input-dependent data structure.

A recursive implementation would use O(h) call-stack space.

C++ Solution: Iterative BST Search

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode* left;
 *     TreeNode* right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(
        TreeNode* root,
        TreeNode* p,
        TreeNode* q
    ) {
        TreeNode* current = root;

        while (current != nullptr) {
            if (p->val < current->val &&
                q->val < current->val) {
                current = current->left;
            } else if (p->val > current->val &&
                       q->val > current->val) {
                current = current->right;
            } else {
                return current;
            }
        }

        return nullptr;
    }
};

Walkthrough

Use the following input:

root = [5,3,8,1,4,7,9,null,2]
p = 3
q = 4

The relevant part of the tree is:

        5
       / \
      3   8
     / \
    1   4
     \
      2

Step 1: Visit Node 5

p = 3
q = 4
current = 5

Both target values are smaller than 5.

3 < 5
4 < 5

Therefore, both nodes are in the left subtree. Move to node 3.

Step 2: Visit Node 3

p = 3
q = 4
current = 3

The first condition is false because p->val is not smaller than 3; it is equal to 3.

The second condition is also false because both values are not larger than 3.

We enter the final else branch and return node 3.

This is correct because node 3 is an ancestor of itself and also an ancestor of node 4.

Recursive Alternative

The same decision process can be written recursively:

class Solution {
public:
    TreeNode* lowestCommonAncestor(
        TreeNode* root,
        TreeNode* p,
        TreeNode* q
    ) {
        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;
    }
};

The recursive version also takes O(h) time, but it uses O(h) call-stack space. The iterative version is preferable when constant auxiliary space is desired.

Common Mistakes

Requiring the Targets to Appear in a Particular Order

A condition such as this is incomplete:

p->val < root->val && q->val > root->val

It handles only one ordering of p and q. The arguments may be supplied in the opposite order.

Instead of testing a specific split orientation, first test whether both nodes are left or both are right. The remaining case automatically represents a split or equality.

Forgetting That a Node Can Be Its Own Ancestor

When current equals p or q, the current node may be the answer.

Using the final else branch correctly handles equality without requiring a separate condition.

Using Generic Binary-Tree DFS

A generic lowest-common-ancestor algorithm works, but it ignores the most useful property of the input: BST ordering.

Using the ordering property avoids searching both subtrees and produces a simpler solution.

Comparing Node Pointers Instead of Values

The direction of traversal depends on the BST values:

p->val
q->val
current->val

Pointer addresses do not describe the ordering of nodes inside the tree.

Accessing a Null Node

When writing a defensive implementation, check that the current pointer is not nullptr before reading current->val.

The official constraints guarantee that both nodes exist, but the iterative loop still makes the pointer safety explicit.

Key Takeaways

1. Use the binary search tree property instead of treating the input as a general binary tree.
2. Continue left when both target values are smaller than the current value.
3. Continue right when both target values are larger than the current value.
4. The first split point—or the first target encountered—is the lowest common ancestor.
5. An iterative traversal achieves O(h) time with O(1) auxiliary space.