Wednesday, June 26, 2013

Relation between leaf nodes and non leaf nodes in a Binary Tree

A Binary tree has n leaf nodes. The number of nodes of degree 2 in T is:

a) log2 n         b)  n-1          c) n             d) 2^h

The answer is b) n-1

Let n1 be the number of nodes of degree one
n0 be the number of nodes of degree 0,  leaf nodes are the ones which have degree 0
n2 be the number of nodes of degree 2,  root node is one example of a degree 2 node in the figure below.
n be the total number of nodes in the tree.

we have,   n = n0 + n1 + n2                                                     -------------  1

If we count the number of edges in a binary tree, we see that every node except the root has an incoming edge into it. If E is the number of edges, then n = E + 1, i.e. number of edges in a binary tree is one less than the total number of nodes.

Each n0 node contributes no edge,
each n1 node contributes one edge,
and each n2 node contributes 2 edges to the total number of edges, E.

E = 0*n0 + 1 * n1 + 2* n2
E = n1 + 2n2 
                                                                       
We know that n = E + 1
n = n1 + 2n2 + 1                                                                     -------------- 2

Solving equations 1 and 2, we get

n0 + n1 + n2 = n1 + 2n2 + 1
n0 = n2 + 1

The number of leaf nodes in a binary tree is one more than the number of degree 2 nodes.
In the above binary there are 6 nodes in total, n = 6
We know that n = n0 + n1 + n2
n = 3 + 1 + 2

Also we know that n  = E + 1
E is the total number of edges, E = 5, every node has one incoming edge except the root node.
E = n1 + 2n2
n1 = {2} , which contributes edge 'c'
n2 = {1, 3}, node 1 contributes edges 'a' and 'b',  node 3 contributes edges 'd' and 'e'.
n0  = {4,5,6} doesn't contribute any edge.

E = 1 + 2 * 2 = 5
n = E+ 1 = 6
n0 = n2 + 1 = 2 + 1 = 3

In a ternary tree we have n = n0 + n1 + n2 + n3                   ------------- 3
n3 is the number of nodes of degree 3.

If we count the number of edges in a ternary tree, we see that every node except the root has an incoming edge into it. If E is the number of edges, then n = E + 1, i.e. number of edges in a ternary tree is one less than the total number of nodes.

Each n0 node contributes no edge,
each n1 node contributes one edge,
each n2 node contributes 2 edges,
each n3 node contributes 3 edges to the total number of edges, E.

E = 0*n0 + 1 * n1 + 2* n2 + 3* n3
E = n1 + 2n2 + 3n3 
                                                                       
We know that n = E + 1
n = n1 + 2n2  + 3n3 + 1                                                      -------------- 4

Solving equations 3 and 4, we get

n0 + n1 + n2 +n3= n1 + 2n2 + 3n3 + 1
n0 = n2 + 2n3 + 1                                                              -------------- 5

The number of leaf nodes in a ternary tree of n nodes, with each node having 0 or 3 children is

 n0 = n2 + 2n3 + 1
 n2 = 0, n1 = 0 as there are only nodes having degree 0 or degree 3
 then n0 = 2n3 + 1

we know that n = n0 + n1 + n2 + n3

n = (2n3 + 1) + 0 + 0 + n3
n3 = (n - 1) / 3
then n0 = 2n3 + 1 = 2 ((n-1)/3) + 1 = (2n + 1) / 3 


In an m'ary tree we have n = n0 + n1 + n2 + n3 + ........... +nm
Equation 5 can be generalised to 
n0  = n2 + 2n3 + 3n4 + .........  + (m-1)nm + 1

The number of leaf nodes in a m'ary tree of n nodes, with each node having 0 or m children is

n1= 0, n2 = 0, n3 = 0,.........................nm-1 = 0 as there are only nodes having degree 0 or m
n0 = 0 + 0 + 0 +.............. (m-1)nm + 1
n0 = (m-1)nm + 1

we know that n = n0 + n1 + n2 + n3 + ........... +nm
n = ((m-1)nm + 1) + 0 + 0 +..................................+ nm
n = m*nm  + 1
nm = (n - 1) / m
then n0 = (m-1)nm + 1  = ((m-1) (n-1) / m )+ 1 = (m*n -m -n + m + 1) / m
n0 = (m*n - n + 1) / m  


Share your thoughts in the comments below, to make me describe the blog post  even better and do recommend the post if you found the content helpful!!!

1 comments:

  1. I read this article; it is really informative one. Your way of writing and making things clear is very impressive. I am really impressed by the way you detailed everything. It’s very informative and you are obviously very knowledgeable in this field. Thanks for sharing such an amazing post. Ceed Study Material.

    ReplyDelete