Inserting sorted keys one by one gives the worst BST: a chain. Write BalancedBst: read n and n keys in increasing order, and
- insert them one by one into a plain BST and print its height;
- build a balanced BST with a recursive
build(sorted, low, high)that makes the middle element ((low + high) / 2) the root and builds the two halves as subtrees; print its height; - print the balanced tree level by level with a queue (one line per level);
- print the smallest height any binary tree with n keys can have.
A single node has height 0.
For the input
7
10 20 30 40 50 60 70
the program prints
Inserting in sorted order: height 6
Built from the middle: height 2
level 0: 40
level 1: 20 60
level 2: 10 30 50 70
Smallest possible height for 7 keys: 2