Predecessor and Successor in BST — Problem & Solution
Predecessor and Successor in BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Predecessor and Successor in BST is a medium coding problem on binary search and trees, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Binary Search, Trees
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree with distinct values and an integer key (which may or may not be in the tree).
Return [pre, suc] where pre is the in-order predecessor of key — the largest value in the tree strictly less than key — and suc is its in-order successor — the smallest value strictly greater than key. Use -1 for whichever does not exist.
Example 1
Input: root = [50,30,70,20,40,60,80], key = 65
Output: [60,70]
Explanation: 65 is not in the tree; the closest values around it are 60 and 70.
Example 2
Input: root = [8,1,9,null,4,null,10,3], key = 8
Output: [4,9]
Explanation: 8 is in the tree. Its predecessor is the largest value below it (4) and its successor the smallest above it (9).
Example 3
Input: root = [10,2,11,1,5,null,null,null,null,3,6,null,4], key = 0
Output: [-1,1]
Explanation: Every value is above 0: no predecessor, and the successor is the minimum, 1.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^6all node values are distinct0 <= key <= 10^6
Hints for Predecessor and Successor in BST
Hint 1
The two answers are independent: one is the best value below
key, the other the best above it.Hint 2
For the predecessor, walk down from the root: a value below
keyis a candidate and anything better is in its right subtree; a value at or abovekeysends you left.Hint 3
The successor is the mirror image. Each walk is O(height), and neither needs
keyto be in the tree.
How to solve Predecessor and Successor in BST
Two root-to-leaf walks: one that keeps the last value seen below key (the predecessor), one that keeps the last value seen above it (the successor). Equality simply counts as "not below" or "not above".
Approach
- Predecessor walk: start at the root with
pre = -1. If the node's value is less thankey, setpreto it and go right; otherwise go left. - Successor walk: start at the root with
suc = -1. If the node's value is greater thankey, setsucto it and go left; otherwise go right. - Return
[pre, suc].
Why it works
In the predecessor walk, going right from a candidate discards only smaller values, and going left from a value at least key discards only values at least key, so the largest value below key is never discarded and is the last candidate recorded. The successor walk is symmetric.
Complexity
- Time —
O(h) - Space —
O(1)
Pitfalls
- When
keyis in the tree it is neither its own predecessor nor successor — the comparisons are strict. - Do not assume
keyis present; the walks never need to find it.
Reference solution
Python
from typing import List, Optional
def findPreSuc(root: Optional[TreeNode], key: int) -> List[int]:
pre = -1
node = root
while node:
if node.val < key:
pre = node.val
node = node.right
else:
node = node.left
suc = -1
node = root
while node:
if node.val > key:
suc = node.val
node = node.left
else:
node = node.right
return [pre, suc]Java
public static int[] findPreSuc(TreeNode root, int key) {
int pre = -1, suc = -1;
TreeNode node = root;
while (node != null) {
if (node.val < key) { pre = node.val; node = node.right; }
else node = node.left;
}
node = root;
while (node != null) {
if (node.val > key) { suc = node.val; node = node.left; }
else node = node.right;
}
return new int[] { pre, suc };
}C++
vector<int> findPreSuc(TreeNode* root, int key) {
int pre = -1, suc = -1;
for (TreeNode* node = root; node; ) {
if (node->val < key) { pre = node->val; node = node->right; }
else node = node->left;
}
for (TreeNode* node = root; node; ) {
if (node->val > key) { suc = node->val; node = node->left; }
else node = node->right;
}
return {pre, suc};
}JavaScript
var findPreSuc = function(root, key) {
var pre = -1, suc = -1, node = root;
while (node !== null) {
if (node.val < key) { pre = node.val; node = node.right; }
else node = node.left;
}
node = root;
while (node !== null) {
if (node.val > key) { suc = node.val; node = node.left; }
else node = node.right;
}
return [pre, suc];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 189 binary search problems · the whole catalogue
Learn the technique: Binary Search · Binary Trees and Tree Traversals