4

I have a tree that has the following form:

enter image description here

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?)?

Oti Na Nai
  • 1,327
  • 4
  • 13
  • 20

5 Answers5

4

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
Amxx
  • 3,020
  • 2
  • 24
  • 45
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.

Community
  • 1
  • 1
Ashesh
  • 3,499
  • 1
  • 27
  • 44
  • 1
    note: down vote was a result of posting wrong equation (mixed up html tags for superscript). Errors have been rectified. – Ashesh Apr 27 '15 at 03:27
1

The number of nodes in a complete tree is...

n = 2^(h+1) - 1.

ChiefTwoPencils
  • 13,548
  • 8
  • 49
  • 75
1

What you're describing sounds like "a perfect binary tree". "a binary tree is a tree data structure in which each node has at most two children" http://en.wikipedia.org/wiki/Binary_tree A perfect tree is "A binary tree with all leaf nodes at the same depth." http://xlinux.nist.gov/dads//HTML/perfectBinaryTree.html

height to maximum number of nodes in perfect binary tree =2^(height+1)-1

number of nodes to minimum height =CEILING(LOG(nodes+1,2)-1,1)

Definitions associated with Binary trees can be found at the Wikipedia wiki cited earlier.

Bryan Ritter
  • 123
  • 1
  • 7
0

This can also be understood like this.

In case of a perfect binary tree total number of leaf nodes are 2^H (H = Height of the tree)

and total number of internal nodes are 2^H - 1

Hence the total number of nodes will be 2^H + 2^H - 1 which is 2^(H+1) - 1 as mentioned by others.

Hope this will help.

V Chauhan
  • 1
  • 1