educative.io

Educative

Minimum Number of Nodes

A reader asked us the following:

It seems that there is a typo for those values which should be: Full Binary Tree: 2^h + 1

Hi,

This is Maida Ijaz from Educative. For the full binary tree, the minimum number of nodes should be 2h+1, not 2^h+1. Because at each level, we must have two nodes minimum except for the first level, which has one node(root node). So, if h = 3 then the minimum number of nodes present in a full binary tree will be:

1+ 2+ 2+ 2 = 7

Let’s calculate it from the formula:

2h+1 = 2(3)+1 =7

If we use 2^h+1, then the minimum number of nodes will be 2^3+1=9, which is not true.

We hope Educative has inspired to further your learning.

Best Regards,

Maida| Developer Advocate

educative.io

1 Like