7.1.1 Depth versus Capacity*

*This section can be omitted on first reading.

Let us take a moment here to derive two important relations between the depth, d and the number of nodes, n, in a binary tree. First note that in any binary tree there is at most one node at depth 1, at most two nodes at depth 2, and, in general, at most 2^k-1 nodes at depth k, since a node can give rise to at most two nodes at the next depth. The total number of nodes, n, is then at most 1 + 2¹ + 2² + ^{. . .} + 2^d-1. This sum is 2^d - 1. So

n ?/FONT> 2d - 1

The minimum possible depth, d_min, for a binary tree with n nodes will be given by

dmin = ?/FONT>lg (n + 1)?/FONT>

where ?/FONT>x?/FONT> indicates the smallest integer that equals or exceeds x. If n = 20, then d_min = ?/FONT>lg 21?/FONT> = ?/FONT>4.39?/FONT> = 5; and if n = 31, then d_min = ?/FONT>lg 32?/FONT> =5. The binary tree corresponding to d_min may always be taken as a complete binary tree. Consequently, the depth of a complete binary tree will never exceed (lg n) + 1. This contrasts sharply with the depth of the sparsest binary tree with n nodes, which is n . For instance, if n is 1,000, the complete binary tree has a depth of only 10, while the sparsest has depth 1,000. This has important implications for how trees are constructed and for information retrieval, as shown in Chapter 9.