Design Gurus Logo
Inorder Successor in BST (medium)

Problem Statement

Given a root node of the binary search tree and node p, return the value of the in-order successor of node p in the given tree. If the given node has no in-order successor, return -1.

The in-order successor of a node is the next node in the in-order traversal of the BST, which means it is the node with the smallest value greater than the given node.

Examples

Example 1:

  • Input: root = [3,2,4,1], p = 2
Image
  • Expected Output: 3
  • Justification: In the in-order traversal [1,2,3,4], the next node after 2 is 3, making it the in-order successor.

Example 2:

  • Input: root = [8,3,10,1,6,null,14,null,null,4,7,13], p = 6
Image
  • Expected Output: 10
  • Justification: The in-order traversal of the tree is [1,3,4,6,7,8,10,13,14]. The smallest value greater than 6 is 7, making it the in-order successor.

Example 3:

  • Input: root = [15,10,20,8,12,16,25], p = 25
Image
  • Expected Output: -1
  • Justification: In the in-order traversal [8,10,12,15,16,20,25], there is no node after 25. Hence, the expected output is -1.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory