codejump
MediumPro challengePythonJavaScriptTypeScript

BST — Inorder Successor

Data StructuresTreesBinary Search Tree

solve(levelOrder, p) — in a binary search tree with unique values, return
the inorder successor of the node holding p: the smallest value in the
tree that is strictly greater than p. Return -1 when there is none.
p is guaranteed to be in the tree.

You do not need parent pointers or a full traversal: use the BST ordering to find
it in O(h).

Examples (tree [5, 3, 6, 2, 4, null, null, 1])

solve(tree, 1)  → 2
solve(tree, 3)  → 4
solve(tree, 4)  → 5   // the answer is an ancestor
solve(tree, 6)  → -1

Sample tests

Test #1Successor is the parent
Input: [[5,3,6,2,4,null,null,1],1]
Output: 2
Test #2Successor is the leftmost node of the right subtree
Input: [[5,3,6,2,4,null,null,1],3]
Output: 4
Test #3Successor is a higher ancestor
Input: [[5,3,6,2,4,null,null,1],4]
Output: 5
← All challenges