Find the Second Smallest Element in a Binary Search Tree

You are given a sequence of n integers representing the order of insertion into a binary search tree (BST). Your task is to construct the BST and determine the second smallest element in the tree. The BST is built by inserting the values one by one in the given order. If the tree does not contain at least two nodes, output None.

Note: The in-order traversal of a BST produces the values in sorted order. The second value in this order is the second smallest element.

It is guaranteed that all inserted values are unique.

inputFormat

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

• The first line contains a single integer n (n ≥ 1), the number of nodes in the tree.
• The second line contains n space-separated integers indicating the insertion order into the BST.

outputFormat

Output the second smallest element in the BST to stdout. If the BST has fewer than 2 nodes, output None.

1
1

None