How do you approach Lowest Common Ancestor of a BST?

In a general binary tree this needs a full search. In a BST, the values themselves tell you which way to go.

What is the time complexity of Lowest Common Ancestor of a BST?

Time complexity: O(h). Space complexity: O(1) with the iterative form..

What are common mistakes on Lowest Common Ancestor of a BST?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Lowest Common Ancestor of a BST

EasyData Structures

Description

Given a **binary search tree** and two values `p` and `q` that both exist in it, return the value of their **lowest common ancestor** - the deepest node having both as descendants. A node is allowed to be a descendant of itself. The tree is given as a **level-order array with explicit nulls**, where the children of index `i` sit at `2i + 1` and `2i + 2`. An empty array is an empty tree.

Example 1

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

Output: 6

Example 2

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

Output: 2

Example 3

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

Output: 2

Constraints

- 2 <= number of nodes <= 10^5 - All node values are unique, and both p and q exist in the tree. - The input is a valid BST.

Lowest Common Ancestor of a BST: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

In a general binary tree this needs a full search. In a BST, the values themselves tell you which way to go.
If both p and q are smaller than the current node, the answer is in the left subtree; if both are larger, it is in the right.
The moment they land on opposite sides - or one equals the current node - you are standing on the answer. No recursion needed; a loop works.

The optimal approach

Show the approach: The split point is the answer

The general-tree version of this problem requires searching both subtrees and combining results. A BST makes it almost trivial, because comparing values tells you where each target lives without looking.

Descend from the root. While both targets are less than the current value, both are in the left subtree, so move left; while both are greater, move right. The first node where they diverge - one on each side, or one equal to the current node - is the lowest common ancestor, because any deeper node would have both targets on the same side of it and could not be an ancestor of both.

That "or one equals the current node" clause is what implements the rule that a node counts as its own descendant, and it is the case people miss.

Since the walk never backtracks, this needs no recursion and no stack - a simple loop in O(1) space. It runs in O(h): O(log n) on a balanced tree, O(n) on a degenerate one.

Time: O(h)
Space: O(1) with the iterative form.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

← Back to problems

Lowest Common Ancestor of a BST

EasyData Structures

Description

Example 1

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

Output: 6

Example 2

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

Output: 2

Example 3

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

Output: 2

Constraints

- 2 <= number of nodes <= 10^5 - All node values are unique, and both p and q exist in the tree. - The input is a valid BST.

Lowest Common Ancestor of a BST: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

In a general binary tree this needs a full search. In a BST, the values themselves tell you which way to go.
If both p and q are smaller than the current node, the answer is in the left subtree; if both are larger, it is in the right.
The moment they land on opposite sides - or one equals the current node - you are standing on the answer. No recursion needed; a loop works.

The optimal approach

Show the approach: The split point is the answer

That "or one equals the current node" clause is what implements the rule that a node counts as its own descendant, and it is the case people miss.

Since the walk never backtracks, this needs no recursion and no stack - a simple loop in O(1) space. It runs in O(h): O(log n) on a balanced tree, O(n) on a degenerate one.

Time: O(h)
Space: O(1) with the iterative form.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.