Inorder Successor in BST

MediumTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a binary search tree with distinct values and an integer p that is the value of one of its nodes. Return the value of the **in-order successor** of that node: the node visited immediately after it in an in-order traversal, which is the node with the smallest value strictly greater than p. If the node holding p is the largest value in the tree, it has no successor; return -1 in that case. Try to use the BST ordering so the search takes O(h) time, where h is the tree height.

Examples

Input: root = [2,1,3], p = 1
Output: 2
In-order is 1, 2, 3, so 2 follows 1.
Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: -1
6 is the largest value, so nothing follows it.
Input: root = [5,3,6,2,4,null,null,1], p = 4
Output: 5
4 has no right child, so its successor is the nearest ancestor it sits to the left of: 5.

Constraints

  • 1 <= number of nodes <= 10^4
  • -10^5 <= Node.val <= 10^5
  • All values are distinct
  • `p` is the value of a node in the tree

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems