Find the Second Largest Element in a Binary Search Tree

You are given a list of unique integers that will be inserted into an initially empty Binary Search Tree (BST) in the given order. Your task is to find and print the second largest element in the BST.

If the BST contains fewer than two nodes, print None.

The BST is built by inserting nodes in the order they are given, following the BST property: for any node, all nodes in its left subtree are less than the node's value, and all nodes in its right subtree are greater.

Hint: Consider two cases: (1) the largest node has a left subtree, in which case the second largest is the maximum value in that left subtree, and (2) the largest node has no left subtree, so its parent is the second largest.

The formula for the solution can be expressed as: $$\text{{second_largest}} = \begin{cases} \max(\text{{left subtree of largest}}) & \text{if largest has a left subtree} \\ \text{{parent of largest}} & \text{otherwise} \end{cases}$$

inputFormat

The first line of input contains an integer n representing the number of nodes in the BST. The second line contains n space-separated integers which are the node values inserted in order into the BST.

outputFormat

Output a single line with the value of the second largest element in the BST. If no such element exists, output None.

1
1

None