The statement is not true. Consider two extreme examples, adding elements in
ascending and descending order. The first one results in a degenerate left
tree, while the second one is a degenerate right tree.