Inorder Successor in BST

Medium

Description

You are given a binary search tree (BST) and the value p of one of its nodes. The in-order successor of that node is the node with the smallest value that is bigger than p. Return the value of the successor. If there is none, return -1.

How the judge passes the data

Examples

Example 1:

Input: root = [20,10,30,5,15,25,40], p = 25
Output: 30
Explanation: The next bigger value after 25 in the tree is 30.

Example 2:

Input: root = [20,10,30,5,15,null,40,null,null,null,18], p = 15
Output: 18
Explanation: The node 15 has a right child 18, and 18 is the next bigger value.

Example 3:

Input: root = [20,10,30,5,15,25,40], p = 40
Output: -1
Explanation: 40 is the biggest value in the tree, so there is no successor.

Tree
Depth-First Search
Binary Search Tree
Binary Tree

Constraints

1 <= Number of nodes <= 10^4
0 <= Node.val <= 10^5
Every node has a different value.

Examples

3 shown

Example 1

Input

[20,10,30,5,15,25,40]
25

Output

Example 2

Input

[20,10,30,5,15,null,40,null,null,null,18]
15

Output

Example 3

Input

[20,10,30,5,15,25,40]
40

Output

-1

Opening the editor...