Inorder successor and predecessor in a BST

Medium

Problem

Given a BST and a key (which may or may not be in the tree), return the in-order predecessor (the largest value smaller than the key) and successor (the smallest value larger than the key).

Example 1

Input:  BST [50, 30, 70, 20, 40, 60, 80], key = 65
Output: predecessor 60, successor 70

Also asked as: Find inorder successor and inorder predecessor in a BST · Populate Inorder successor of all nodes

Test cases

Case 1

Input:    [50,30,70,20,40,60,80], 65
Expected: 70

Case 2

Input:    [50,30,70,20,40,60,80], 50
Expected: 60

Case 3

Input:    [50,30,70,20,40,60,80], 10
Expected: 20

Case 4

Input:    [50,30,70,20,40,60,80], 80
Expected: null

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Descend, remembering the last turn

Time O(h)Space O(1)

Successor: go right and take the leftmost; if no right child, it is the last ancestor you turned left from. Predecessor is the mirror.

function inorderSuccessor(root, key) {
let succ = null, n = root;
while (n) {
if (key < n.val) { succ = n; n = n.left; }
else n = n.right;
}
return succ;
}
// Populate .next for every node: reverse in-order traversal, keeping a running "next".