Height and complete trees

The height of a tree is the length of the longest path from the root to a leaf (conventions vary by 1; here: a leaf has height 0). A complete binary tree fills levels from left to right.

In a balanced tree, the height grows slowly with the number of nodes. In a degenerate chain, it grows proportionally to the number of nodes.

Many algorithms depend on height (search, insertion).

$$h_{\mathrm{complete}} = \lfloor \log_2 n \rfloor$$

$$h_{\mathrm{complete}}=\lfloor \log n \rfloor$$

Where used

Balancing, worst-case search, memory layout of heaps. The height controls the latency of search structures and the stack depth of recursive walks.

Depth

The height measures the longest root-to-leaf path, depending on the convention in edges or nodes. This convention changes base values for empty trees and leaves, but not the asymptotic statement.

A fully filled tree doubles the maximum number of nodes with each additional level. Therefore, a height that is small in relation to the number of nodes is sufficient. A heavily unbalanced tree loses this advantage and behaves structurally like a list.

Full, perfect, and complete denote different structural conditions. For heap implementations, it is particularly important that all levels are filled except for the last, and that the last is filled from the left.

Difficulty levels

1. Calculate height according to a specified convention.
2. Relate the number of nodes and levels of a perfect tree.
3. Distinguish between perfect, complete, and unbalanced shapes.

Pitfalls

Without a specified convention, height values are ambiguous by one. A large number of nodes also does not guarantee a small height if there is no balance condition.