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

# Almost complete binary tree

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2070 Magh, 2 marks
- Video: [Lec-52: Introduction to Trees | Binary Tree, Almost Complete Binary Tree, Full BT, Complete](https://www.youtube.com/watch?v=z0Vnno96_MA) — Gate Smashers
- 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-binary-tree
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

What is an almost complete binary tree?

## Short answer

An almost complete binary tree has all levels full except possibly the last, which is filled from left to right with no gaps. It can be stored efficiently in an array, with children of node i at 2i+1 and 2i+2.

## Answer

An **almost complete binary tree** of depth d is a binary tree in which:

1. Every level from 0 to d − 1 is completely filled (level k has 2ᵏ nodes), and
2. The nodes of the last level d are placed as far left as possible, with no gaps between them.

So the tree is full except possibly for the last level, which is filled from left to right. Such a tree can be stored in an array without wasted space, with the children of node *i* at 2i+1 and 2i+2 (0-based). Heaps are almost complete trees.

```text
        A
      /   \
     B     C
    / \   /
   D   E F
```
Levels 0 and 1 are full; the last level holds D, E, F from the left with no gap, so this tree is almost complete. If F were the right child of C (with C's left child missing), there would be a gap and the tree would not be almost complete.

## Check yourself

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

1. What defines an almost complete binary tree of depth d?
   A. All levels are full including the last
   B. Levels 0 to d-1 are full, and the last level is filled from the left with no gaps
   C. Every node has either 0 or 2 children
   D. The last level is filled from the right
   Answer: B. Only the last level may be partly filled, and its nodes must be packed to the left. (Key point: Definition)

2. In an array (0-based) representation, where are the children of node i?
   A. 2i and 2i+1
   B. i+1 and i+2
   C. i/2 and i/2+1
   D. 2i+1 and 2i+2
   Answer: D. Because there are no gaps, children of node i are stored at 2i+1 and 2i+2. Heaps use this layout. (Key point: Array storage)

3. Which tree is NOT almost complete?
   A. A tree with last level D, E, F packed from the left
   B. One where C's left child is missing but F is C's right child
   C. A single node
   D. A full tree with 7 nodes
   Answer: B. A gap in the last level (missing left child while a right child exists) violates the left-packing rule. (Key point: Counter example)

## Related in Data Structure and Algorithm

- [Almost complete tree; depth of complete tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aalmost-complete-depth-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
- [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