# Why the height of the weight balanced tree is logarithmic

Could somebody explain to me why the height of a weight balanced binary tree in $O(\log n)$ in the worst case?

• It isn't, if the tree limits the out-degree of nodes to 1. Otherwise, for example in the case of AVL trees, because the number of elements is exponential in the depth, which follows from the respective proofs of that property. – G. Bach Sep 22 '13 at 18:22
• I explain it here stackoverflow.com/a/13093274/550393 – 2cupsOfTech Apr 10 '14 at 15:48

In particular, you're going to want to look at a proof by induction. Does a tree with 1 node have logarithmic height? Then look at a tree with $n$ nodes. When you add another node to a balanced binary tree, which you know to have logarithmic height, what is the worst thing that can happen to the height?