A dispatcher inserts distinct integer priorities into a binary search tree, one at a time, in the order given (standard BST insertion: go left when the new priority is smaller than the current node, otherwise go right). The insertion order fully determines the tree's shape. Report the height of the resulting tree, measured as the number of edges on the longest path from the root down to a leaf. A tree with a single node has height 0.
Line 1: an integer n, the number of priorities.
Line 2: n space-separated distinct integers, the priorities in insertion order.
A single integer: the height of the constructed BST, in edges.
Example 1
Input
7 40 20 60 10 30 50 70
Expected
2
Explanation
40 is the root; 20 and 60 are its children; 10, 30, 50, 70 form the next level. The longest root-to-leaf path (e.g. 40 -> 20 -> 10) has 2 edges, so the height is 2.
Example 2
Input
4 1 2 3 4
Expected
3
Explanation
Inserting in increasing order makes a right-leaning chain 1 -> 2 -> 3 -> 4. The path from root to the deepest leaf has 3 edges, so the height is 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →