Inorder Successor

Given a binary search tree root containing unique values, and an integer t, return the value of the inorder successor of t. That is, return the smallest value greater than t in the tree.

Note: you can assume that the inorder successor exists.

Bonus: solve it in \(\mathcal{O}(h)$` time and `$\mathcal{O}(1)\) space where h is the height of the tree.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Inorder-Successor

Examples

Example 1

Input

• root =

• t = 2

Output

• answer = 3

Example 2

Input

• root =

• t = 1

Output

• answer = 2

Solution