Inorder successor and predecessor in a BST
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
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".