Find the Inorder Successor in a Binary Search Tree

You are given a sequence of n integers which are inserted into a Binary Search Tree (BST) in the order they are provided. Given a target value, your task is to find the inorder successor of the node with that target value in the BST.

The inorder successor of a node in a BST is defined as the node with the smallest key greater than the target node's key. Formally, if a node v has a right subtree, its inorder successor is the node with the minimum key in that right subtree. Otherwise, it is the lowest ancestor of v such that v is in the left subtree of that ancestor. This can be written in LaTeX as: $$\text{successor}(v)=\begin{cases}\min(\{ x \in \text{right subtree of } v \}) &\text{if } v\text{ has a right child}\\ \min(\{ a \,|\, v \text{ is in the left subtree of } a \}) &\text{otherwise}\end{cases}$$

If the target node is not found in the BST or if it has no inorder successor, output null (without quotes).

inputFormat

The input is read from stdin and consists of three lines:

1. The first line contains an integer n denoting the number of nodes in the BST.
2. The second line contains n space-separated integers, representing the values to be inserted into the BST in the given order.
3. The third line contains a single integer representing the target value.

outputFormat

Output a single value to stdout: the inorder successor of the target node. If the target node does not exist in the BST or it does not have an inorder successor, output null (without quotes).

7
20 8 22 4 12 10 14
8

10