Find the kth Smallest Element in a BST

You are given a binary search tree (BST) and an integer k. Your task is to find the kth smallest element in the BST. In a BST, for any node, all elements in its left subtree are smaller and all elements in its right subtree are larger. The kth smallest element is the one which would appear in the kth position if the elements were sorted in ascending order.

Recall that the in-order traversal of a BST yields the nodes in non-decreasing order. Thus, one standard approach is to perform an in-order traversal and keep a count until the kth element is reached.

Mathematically, if the in-order traversal gives elements \( a_1, a_2, \ldots, a_n \), then you need to output \( a_k \) for the given k.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. An integer n representing the number of nodes to insert into the BST.
2. n space-separated integers. Insert these integers into the BST in the given order. It is guaranteed that the resulting tree is a valid BST.
3. An integer k representing the position (1-indexed) of the smallest element to find.

For example, consider the input:

7
5 3 7 2 4 6 8
3

This corresponds to a BST built by inserting 5, 3, 7, 2, 4, 6, 8 in that order and asking for the 3rd smallest element.

outputFormat

Output a single integer via standard output (stdout), which is the kth smallest element in the BST.

For the sample input above, the output should be:

4

## sample

7
5 3 7 2 4 6 8
3

4