Skip to main content

Almost complete tree; depth of complete tree

Short answer

An almost complete binary tree has all levels full except possibly the last, which is filled left to right. For a complete binary tree with depth d and T nodes, T = 2^(d+1) - 1, so d = log2(T+1) - 1.

Define an almost complete binary tree. Show that the depth of complete binary tree is log2(T + 1) - 1 where T is the total number of nodes in a tree.

Definition

An almost complete binary tree of depth d has all levels 0 to d − 1 completely filled, and the last level d has its nodes packed from the left with no gaps. It is called a complete binary tree (strictly, a full one) when the last level is also completely filled.

Proof of depth

Let the complete binary tree have depth d (root at level 0) and T total nodes. Level k has 2ᵏ nodes, so

T = 2⁰ + 2¹ + 2² + ... + 2ᵈ
  = (2^(d+1) − 1) / (2 − 1)          (sum of a geometric series)
  = 2^(d+1) − 1

Hence

T + 1     = 2^(d+1)
log₂(T+1) = d + 1
d         = log₂(T + 1) − 1

Check: T = 7 gives d = log₂ 8 − 1 = 2, which is correct for a tree with levels of 1, 2 and 4 nodes. ∎

For an almost complete tree with T nodes the depth is ⌊log₂ T⌋.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →