Number of nodes of a tree where each node has two children nodes

Question

I have a tree that has the following form:

On the first pictures, the height of the tree is 1 and there are 3 total nodes. 2 for 7 on the next and 3 for 15 for the last one. How can I determine how many number of nodes a tree of this form of l height will have? Also, what kind of tree is that (is it called something in particular?)?

Answer 1

That is a perfect binary tree

You can get the number of node considering this recursive approch:

n(0) = 1
n(l+1) = n(l) + 2^l

so

n(l) = 2^(l+1) - 1

Answer 2

A complete binary tree at depth ‘d’ is the strictly binary tree, where all the leaves are at level d.

• for fig1, d=1
• for fig2, d=2
• for fig3, d=3

So, Suppose a binary tree T of depth d. Then at most

2(d+1)-1

nodes n can be there in T.

• for fig1, d=1; 2(1+1)-1=2(2)-1=4-1=3
• for fig2, d=2; 2(2+1)-1=2(3)-1=8-1=7
• for fig3 d=3; 2(3+1)-1=2(4)-1=16-1=15

The height(h) and depth(d) of a tree (the length of the longest path from the root to leaf node) are numerically equal.

Here's an answer detailing how to compute depth and height.