Maximum Element in a Binary Search Tree

You are given a binary search tree (BST). The BST has the property that for any node with value v, all values in its left subtree are less than v and those in its right subtree are greater than or equal to v. Your task is to find the maximum element in the BST. If the BST is empty, output -1.

You may note that the maximum value in a BST can be obtained by repeatedly following the right child pointer until none exists. Formally, if we denote the maximum value of a non-empty tree by \(\max(T)\), then \[ \max(T) = \begin{cases} -1, & \text{if } T \text{ is empty}\\ \text{value of the rightmost node}, & \text{otherwise} \end{cases} \]

The input is given as a sequence of numbers that are inserted into the BST in the given order according to the BST property.

inputFormat

The first line contains an integer n representing the number of nodes in the BST. If n > 0, the second line contains n space-separated integers indicating the node values in the order in which they should be inserted into the BST. If n = 0, the BST is empty.

outputFormat

Output a single integer which is the maximum value in the BST. If the tree is empty, output -1.

1
5

5