Question

(Algorithm)

A binary tree has a height of h=4. What is the number of nodes of this binary tree if the tree is:

a) A full binary tree

b) A complete binary tree

Answer 1

Here, we have height h of a given tree is 4.

i.e. h = 4

Full binary tree :-

A tree is said to be full binary tree if every node has 0 or 2 childrens except leaf nodes.

So, for h=4 we have possibly,

9, 11, 13 and 15 nodes i.e.

Here, we see that all the trees are full binary trees as all all them have 0 or 2 childrens except leaf node.

So, for h = 4 the possible numbers of nodes for full binary tree are 9, 11, 13 and 15.

Complete binary tree :-

In complete binary tree we have all the levels are completely filled except possibly the last level and last level have keys as left as possible.

So, for h = 4 we have possibly,

8, 9, 10, 11 and 15 nodes i.e.

Here, we see that all the all the levels except the last level is completely filled and all the leaves in the last level are all to the left side.

So, for h=4 the number of nodes for complete binary tree are 8, 9, 10, 11 and 15.

Thumbs up!