Find Minimum Element in a Binary Search Tree

You are given the root of a binary search tree (BST). A BST is a binary tree in which for every node, all elements in its left subtree are strictly less than the node and all elements in its right subtree are strictly greater than the node. Your task is to find and output the minimum element in the tree.

If the tree is empty, output None.

Note: The tree is provided as a list of nodes in level order. Each node is described by its value and the indices of its left and right children (use -1 if a child does not exist). The root of the tree is always the first node in the list.

The BST property guarantees that the minimum element is located at the leftmost node in the tree. In \(\LaTeX\) form, if \(T\) is a BST with root \(r\), then the minimum element is given by:

\[ \min(T) = \begin{cases} \text{None}, & \text{if } T \text{ is empty},\\ \min(T) = r, & \text{if } r \text{ has no left child},\\ \min(T) = \min(\text{left subtree of } r), & \text{otherwise}. \end{cases} \]

inputFormat

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

 n
 value_0 left_0 right_0
 value_1 left_1 right_1
 ...
 value_{n-1} left_{n-1} right_{n-1}

Where:

• n is the number of nodes in the tree. If n is 0, the tree is empty.
• Each of the next n lines contains three integers: the value of the node, the index of the left child, and the index of the right child (indices are 0-based). A value of -1 indicates that the child does not exist.
• The root of the tree is the node at index 0.
</p>

outputFormat

Output via standard output (stdout) the minimum element in the BST. If the tree is empty, print None (without quotes).

## sample

0

None