> We saw that requiring the tree be perfectly balanced is too strong an invariant for a balanced BST,
> because it only allows trees of certain sizes. Alternatively, we could have the invariant that the
> tree is complete, like we did for binary heaps. But this doesn’t work well. Why not?

For a complete tree of a given size, there is only one possible shape
the tree can have. In particular, there is only one complete BST
containing the values {1..n}.

Since there is only one possible shape for the tree, and the values have to
be placed according to the inorder traversal of the tree.

Then, if you insert the value 0 into the tree, every value moves to
a different position, which must take O(n) time.

More on complete vs balanced:
----------------------------

Completeness is a weaker requirement than perfectly balanced, 
but stronger requirement than being balanced.

Balanced says the difference in heights between the left and
right child of any node must be 1. While, completeness says that
the all levels except last must be "full", and last level must be
"full" on the left.

Every complete tree is balanced [why? :)], but every balanced tree
is not complete (counter example below.)

    1
     \
      2