Almost complete binary tree

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.

        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.