Oti Na Nai
Oti Na Nai

Reputation: 1407

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

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

Upvotes: 4

Views: 885

Answers (5)

V Chauhan
V Chauhan

Reputation: 1

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.

Upvotes: 0

Ashesh
Ashesh

Reputation: 3599

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.

Upvotes: 2

Bryan Ritter
Bryan Ritter

Reputation: 123

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.

Upvotes: 1

Amxx
Amxx

Reputation: 3070

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

Upvotes: 4

ChiefTwoPencils
ChiefTwoPencils

Reputation: 13950

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

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

Upvotes: 1

Related Questions