Closest Value in Binary Search Tree

Given a binary search tree (BST) constructed by inserting nodes in the given order, your task is to find the value in the BST that is closest to a specified target integer.

A BST is defined such that for any node with value \(v\), all values in its left subtree are less than \(v\) and all values in its right subtree are greater than \(v\). The insertion of nodes must follow these rules.

Once the tree is constructed, search for the node whose value is the closest (in terms of absolute difference) to the given target. If there are two numbers with the same difference, returning either is acceptable by the problem's constraints.

inputFormat

The input is provided via standard input (stdin) with the following format:

• The first line contains an integer \(n\), representing the number of nodes in the BST.
• The second line contains \(n\) space-separated integers, representing the node values to be inserted into the BST in the given order.
• The third line contains a single integer representing the target value.

outputFormat

Output the value in the BST that is closest to the specified target. The result should be printed to standard output (stdout).

5
10 5 15 3 7
6

5