Predecessor and Successor

Given the root of a binary search tree and an integer key, find the predecessor and successor of key in the BST and return them as a two-element array [predecessor, successor].

The predecessor is the largest value that is strictly less than key.
The successor is the smallest value that is strictly greater than key.

If either does not exist, use -1 in its place. The key may or may not be present in the tree. The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

You don't need to sort the whole tree — use the BST ordering.

Walk down: a node below the key is a predecessor candidate (go right); above is a successor candidate (go left).

If you land on the key, its predecessor is the rightmost node of the left subtree and its successor the leftmost of the right.

Common doubts

The two-descent still works: it converges on the largest value below the key and the smallest above it.

The minimum of the tree has no predecessor and the maximum has no successor; -1 signals 'none'.

Only if you already have the inorder array; otherwise the descent is faster and uses O(1) space.

Interview follow-ups

· What an interviewer asks next.

Augment nodes with subtree sizes, or repeatedly take the inorder predecessor k times.

Define strict vs non-strict neighbours explicitly; duplicates would need a tie-breaking rule.

Fun facts

The predecessor/successor descent is the same skeleton as searching for a key — you just keep the last turn each way.
In a balanced BST this is O(log n); in a skewed one it degrades to O(n), like all BST walks.

Asked at

AmazonMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: root = [8, 4, 12, 2, 6, 10, 14], key = 6
Output: [4, 8]
The largest value below 6 is 4; the smallest above 6 is 8.

Example 2

Input: root = [8, 4, 12, 2, 6, 10, 14], key = 2
Output: [-1, 4]
2 is the minimum, so there is no predecessor; the successor is 4.

Constraints

- The number of nodes is in the range [1, 10^4] - 1 <= Node.val <= 10^5 - All Node.val are unique - 1 <= key <= 10^5

You could flatten the BST to a sorted array (inorder) and scan for the neighbours of key, but that's O(n) time and space. The BST ordering gives a two-descent answer in O(height): keep two candidates and update them as you walk down.

Descend from the root. If the current node is below key, it's a possible predecessor — record it and go right (something bigger but still under key may lie there). If it's above key, it's a possible successor — record it and go left. If you land on key, the true neighbours are in its subtrees: the predecessor is the rightmost node of the left subtree, the successor is the leftmost node of the right subtree.

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left < node < right, everywhere.

Subtree extremes. Rightmost of left subtree = predecessor; leftmost of right = successor.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Is the key guaranteed to be in the tree?”

Not necessarily — handle both present and absent keys.

“What if there is no predecessor or successor?”

Return -1 for the missing one.

The ideal opening — say it like this

I walk down keeping two candidates: nodes below the key update the predecessor, nodes above update the successor.

If I land on the key, the predecessor is the max of its left subtree and the successor the min of its right.

Understand the problem

Worked example — BST [8, 4, 12, 2, 6, 10, 14], key = 6

8  > 6 -> succ = 8, go left
4  < 6 -> pred = 4, go right
6  == 6 -> no left/right child of 6 here -> pred stays 4, succ stays 8
answer = [4, 8]

Key observations

1Aha

Moving right updates the predecessor

A node smaller than the key is a predecessor candidate; going right may find a larger-but-still-smaller one.

2Aha

Moving left updates the successor

A node larger than the key is a successor candidate; going left may find a smaller-but-still-larger one.

3Aha

On the key, look in the subtrees

Predecessor = rightmost of the left subtree; successor = leftmost of the right subtree.

Brute force vs optimal

	Sorted inorder scan	Two-descent
Idea	Flatten to a sorted array, scan for neighbours	Track two candidates while walking down
Time	O(n)	O(height)
Space	O(n)	O(1)

Both return the same pair; the descent uses the ordering to avoid touching every node. Full code is in the Approaches selector below.

Summary

Key takeaway

Walk down the BST tracking a predecessor and a successor candidate; below the key updates the predecessor (go right), above updates the successor (go left). On the key, take the extremes of its subtrees. O(height) time, O(1) space.

while node:
    if node < key: pred = node; go right
    elif node > key: succ = node; go left
    else: pred = max(left subtree); succ = min(right subtree); stop