# Interview Questions

# Almost complete Binary Tree

- June 17, 2016
- Posted by: Kamal Rawat
- Category: Algorithms

A complete Binary tree of height **h** has 2^{h}-1 nodes. Out of these 2^{h-1} are leaf nodes and rest (2^{h-1}-1 are non-leaf. Read more about complete binary trees here or watch video. Below are all complete binary trees:

- There is no hole in complete binary tree. It has maximum number of nodes possible for any binary tree of a particular height

- All non-leaf nodes will have both the children.

None of the below trees is complete binary tree:

### Canonical labeling of nodes

Label the Nodes in the level-wise fashion from left to right, as shown below:

The advantage of canonical labeling is that such a tree can be stored in an array where value of a node is stored at the index equal to its label in the tree.

This way we will save a lot of memory because we do not need to store all the pointers. If you have noticed, there is a relationship between the labels of a node and its children above:

This way, it becomes easy to move in either upward or downward direction of a tree, even when it is stored in an array.

### Almost Complete Binary Tree

A the binary tree made up of the first n nodes of a canonically labeled complete Binary Tree is called Almost complete Binary Tree. Below are all almost complete binary trees,

Below trees are **NOT** almost complete binary trees (the labeling has no meaning, because there are gaps).

As seen above an almost complete binary tree can be stored in an array.

We have earlier written code to check is a given tree is an Almost complete binary tree or not.

Kamal Rawat Agreed

Kamal Rawat Agreed

1. All Leaf nodes of complete binary tree are at same level – False

2. In complete binary tree, there will never be a node that has only one child and the other child is NULL – False

A complete Binary tree of height h has ((2 to the pow of h)-1) nodes is wrong. This property is true for full binary tree.

*A complete Binary tree of height h has atleast (2 to the pow of h-1) nodes and atmost ((2 to the pow of h)-1) nodes