Jun 172016
 

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

complete binary treecomplete binary tree_1

 

 

 

 

1. All Leaf nodes of complete binary tree are at same level
2. In complete binary tree, there will never be a node that has only one child and the other child is NULL

None of the below trees is complete binary tree:

not_complete_binary_tree

Canonical labeling of nodes

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

canonically labeled

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.

Binary heap

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:

Binary heap_1

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,

almost complete binary tree

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

NOT almost complete binary tree

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

3. Every almost complete binary tree is also 'Complete Binary tree'

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

  4 Responses to “Almost complete Binary Tree”

Comments (4)
  1. Kamal Rawat Agreed

  2. Kamal Rawat Agreed

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

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

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)