Balanced binary trees
A binary tree of depth d is balanced if all nodes at depths 0, 1, …, d–2 have two children.
- Nodes at depth d–1 may have two/one/no children.
- Node at depth d have no children (by definition).
- A binary tree of depth 0 or 1 is always balanced.
A balanced binary tree of depth d has at least 2d and at most 2d+1 – 1 nodes. Conversely:
Depth of balanced binary tree of size n = floor(log2 n)
An ill-balanced binary tree of depth d could have as few as d+1 nodes. Conversely:
Max. depth of ill-balanced binary tree of size n = n–1