Number of nodes in tree

So, if we want to know the number of nodes at a height, then:

 

                      4️⃣                  - > Number of nodes = 2^0 = 1                   

                 /          \                   

              3️⃣              5️⃣        - > Number of nodes = 2^1 = 2

           /      \          /     \

        1️⃣        2️⃣     6️⃣       7️⃣        - > Number of nodes = 2^2 = 4

 

In the above tree, the maximum height of a node is 2 i.e. of the root node. The height of tree is the maximum node height in tree, so

Height of tree, h = 2

 

Let's think in terms of total number of nodes, n in tree

nmax = 2^0 + 2^1 + ... + 2^(h-1) + 2^(h)

The above equation will result in:

nmax = 2^(h+1) - 1

If you think deeply, then you may find that this is the maximum number of nodes that can be present in a tree.

As in the past, we have read about complete binary tree. If not, then complete binary tree is a tree in which all the levels are filled except possibly the lowest one.

So there, the minimum number of nodes required for a complete binary tree will be:

nmin = 2^0 + 2^1 + ... + 2^(h-1) + 1

You would observe than instead of 2^(h) as last term, I have replaced with 1. This is because, the minimum number of node required for last level to exist is 1.

As it is a complete binary tree, so we assume that all the nodes except the last level should be completely filled i.e. filled to the max capacity.

 

The equation will result in:

nmin = 2^(h) - 1 + 1

nmin = 2^(h)