1 to n are inserted one by one into an initially empty binary search tree, in the order given by keys. The first number becomes the root; each next one walks down from the root, going left when it is smaller than the current node and right when it is larger, and becomes a new leaf in the first empty spot.
Return the height of the resulting tree: the number of nodes on the longest path from the root to a leaf.
Simulating the insertions directly can take O(n²) when the tree degenerates into a chain. Try to do better.keys=[3, 1, 2, 5, 4] → 3
The root is 3; 1 goes left, 2 becomes the right child of 1; 5 is the right child of 3 and 4 the left child of 5. The longest paths, 3 → 1 → 2 and 3 → 5 → 4, have 3 nodes each.
keys=[1, 2, 3] → 3
The keys arrive in increasing order, so the tree becomes a chain going right, of height 3.
keys=[4, 2, 6, 1, 3, 5, 7] → 3
This gives a perfectly balanced tree with three levels.
keys is a permutation of the numbers from 1 to nkeys=[3, 1, 2, 5, 4]
3
Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.