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

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!!!