Inorder Successor in BST — Solution in Python, Java & C++
Inorder Successor in BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Inorder Successor in BST is a medium coding problem on depth-first search, binary search and trees, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, 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 a value x that occurs in the tree.
Return the value of the in-order successor of the node holding x — the node that comes right after it in an in-order traversal, i.e. the smallest value greater than x. If x is the largest value in the tree, return -1.
Example 1
Input: root = [2,1,3], x = 2
Output: 3
Explanation: In increasing order the values are 1, 2, 3; the one after 2 is 3.
Example 2
Input: root = [20,8,22,4,12,null,null,null,null,10,14], x = 14
Output: 20
Explanation: 14 has no right subtree; its successor is the nearest ancestor it lies to the left of — 20.
Example 3
Input: root = [20,8,22,4,12,null,null,null,null,10,14], x = 22
Output: -1
Explanation: 22 is the largest value, so it has no successor.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5all node values are distinctx is the value of a node in the tree
Follow-up: Can you find it in O(height) time?
Hints for Inorder Successor in BST
Hint 1
The successor is the smallest value larger than
x, so you never need the full traversal.Hint 2
If the node of
xhas a right subtree, the successor is that subtree's leftmost node. Otherwise it is an ancestor.Hint 3
Both cases are covered by one walk from the root: at a node larger than
x, remember it and go left; otherwise go right. The last remembered node is the answer.
How to solve Inorder Successor in BST
Search for x from the root, and every time the walk goes left from a value larger than x, record that value: the last one recorded is the smallest value larger than x.
Approach
- Set
succ = -1and start at the root. - If the node's value is greater than
x, setsuccto it and move left (a smaller candidate may be there). - Otherwise move right (everything at or below this node's left is not larger than
x). - When the walk ends, return
succ.
Why it works
Moving left from a candidate discards only values larger than that candidate; moving right from a value at most x discards only values at most x. The smallest value above x is therefore never discarded, and the walk reaches it — either as the last ancestor turned left at, or as the leftmost node of x's right subtree.
Complexity
- Time —
O(h) - Space —
O(1)
Pitfalls
- Stopping when
xis found loses the right-subtree case: keep walking right fromx. - The successor of the maximum does not exist — return
-1, notx.
Reference solution
Python
from typing import Optional
def inorderSuccessor(root: Optional[TreeNode], x: int) -> int:
succ = -1
node = root
while node:
if node.val > x:
succ = node.val
node = node.left
else:
node = node.right
return succJava
public static int inorderSuccessor(TreeNode root, int x) {
int succ = -1;
TreeNode node = root;
while (node != null) {
if (node.val > x) { succ = node.val; node = node.left; }
else node = node.right;
}
return succ;
}C++
int inorderSuccessor(TreeNode* root, int x) {
int succ = -1;
TreeNode* node = root;
while (node) {
if (node->val > x) { succ = node->val; node = node->left; }
else node = node->right;
}
return succ;
}JavaScript
var inorderSuccessor = function(root, x) {
var succ = -1, node = root;
while (node !== null) {
if (node.val > x) { succ = node.val; node = node.left; }
else node = node.right;
}
return succ;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Search