---
title: "Almost complete tree; depth of complete tree"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:almost-complete-depth-proof"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/almost-complete-depth-proof
site: BCT Engineering
---

# Almost complete tree; depth of complete tree

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2071 Magh, 2+3 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/almost-complete-depth-proof
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

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.

## 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.

## Answer

#### 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

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

```text
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⌋.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What distinguishes a complete binary tree from an almost complete one in this answer?
   A. In a complete tree the last level is also completely filled
   B. A complete tree has only left children
   C. A complete tree has no leaves
   D. A complete tree is stored in a linked list
   Answer: A. Almost complete only needs the last level packed to the left; complete means every level including the last is full. (Key point: Definition)

2. For a complete tree of depth d (root at level 0), what is T?
   A. T = 2^d - 1
   B. T = 2^(d+1)
   C. T = 2^0 + 2^1 + ... + 2^d = 2^(d+1) - 1
   D. T = d^2 + 1
   Answer: C. Level k has 2^k nodes; the geometric series sums to 2^(d+1) - 1. (Key point: Node count formula)

3. Starting from T = 2^(d+1) - 1, how is the depth obtained?
   A. T + 1 = 2^(d+1), so d = log2(T+1) - 1
   B. T = 2^d, so d = log2(T)
   C. T - 1 = 2^(d+1), so d = log2(T-1)
   D. T = 2d + 1, so d = (T-1)/2
   Answer: A. Adding 1 to both sides gives a power of two; taking log2 gives d + 1. (Key point: Deriving depth)

4. A complete tree has 15 nodes. What is its depth?
   A. 4
   B. 2
   C. 3
   D. 3.5
   Answer: C. d = log2(16) - 1 = 4 - 1 = 3 (levels with 1, 2, 4, 8 nodes). (Key point: Numerical check)

## Related in Data Structure and Algorithm

- [Almost complete binary tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aalmost-complete-binary-tree) — Data Structure and Algorithm, chapter 6
- [Strictly binary tree has 2n-1 nodes](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astrict-binary-tree-nodes-proof) — Data Structure and Algorithm, chapter 6
- [Binary tree traversals; preorder of BST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-tree-traversal-methods-preorder) — Data Structure and Algorithm, chapter 6
- [Draw binary tree from preorder and inorder](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adraw-tree-from-preorder-inorder) — Data Structure and Algorithm, chapter 6