Find Successor

Given the root of a binary tree and a node in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

The successor here means that the node will be traversed next in an inorder manner for the given node value.

Example

Input

Binary Tree

Target Node = 5

Output

Output = 1

Explanation

The inorder traversal of the given binary tree is

Inorder Traversal = 6, 4, 2, 5, 1, 3

The successor of the node with value 5 is the node with value = 1. Hence, We return the node with value 1.

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105
• All Nodes will have unique values.