The problem. Given the root of a binary search tree and a node p in it, return the in-order successor of p — the node with the smallest value greater than p.val — or null if p holds the largest value.
root = [2, 1, 3], p = 1 -> 2
root = [5, 3, 6, 2, 4, null, null, 1], p = 6 -> null (6 is the largest)
root = [20, 8, 22, 4, 12, null, null, null, null, 10, 14], p = 8 -> 10
root = [20, 8, 22, 4, 12, null, null, null, null, 10, 14], p = 14 -> 20function inorderSuccessor(root, p) { let prev = null, answer = null; const inorder = (node) => { if (node === null || answer !== null) return; inorder(node.left); if (answer === null && prev === p) answer = node; // the node right after p prev = node; inorder(node.right); }; inorder(root); return answer;}Time O(n), space O(h). Works on any binary tree — the ordering is never used.
If p has a right subtree, the successor is that subtree's leftmost node. If not, it's the nearest ancestor for which p lies in the left subtree — the last node where a search for p turned left.
function inorderSuccessor(root, p) { if (p.right !== null) { // leftmost node of the right subtree let node = p.right; while (node.left !== null) node = node.left; return node; } let answer = null, node = root; // search for p; remember the last left turn while (node !== p) { if (p.val < node.val) { answer = node; node = node.left; } else node = node.right; } return answer;}Time O(h), space O(1). Two cases, each one walk down.
Both cases collapse into one loop: walk from the root, and every node bigger than p.val is a candidate — keep it and go left for a smaller one. A node not bigger than p.val can't be the answer — go right. It's the ceil search from the Floor and Ceil lesson, with strictly greater.
Bigger than p: a candidate, go left. Not bigger: go right.
function inorderSuccessor(root, p) { let answer = null; let node = root; while (node !== null) { if (node.val > p.val) { answer = node; // bigger than p: a candidate, look for a smaller one node = node.left; } else { node = node.right; // not bigger: the successor is to the right } } return answer;}Time O(h), space O(1). It never even needs p's node — only its value.
