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

Answers (5)

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

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=2⁽²⁾-1=4-1=3
for fig2, d=2; 2⁽²⁺¹⁾-1=2⁽³⁾-1=8-1=7
for fig3 d=3; 2⁽³⁺¹⁾-1=2⁽⁴⁾-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

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