Tuesday, January 3, 2012

In a non-Empty binary tree Number of nodes of degree two is one less than number of leaf nodes

In a non-Empty binary tree
I.e a binary tree where every node has 2 child nodes or 0 child nodes
or a binary tree where every node has a degree 2 or is a leaf node

To prove : Number of nodes of degree two is one greater than number of leaf nodes
let n0 = no of leaf nodes
n1 = no of nodes with degree 2

then to prove that :
n0 = n1 + 1


Lets go about solving this problem with a simple imagination
Let assume a healthy binary tree to be one where each node is just healthy enough to give rise to 2 other nodes.
But due to some environmental complications, the tree gets diseased or little mutated i.e now every node either give rise to 2 nodes or none at all. So it's kind of saying that the nodes have now developed a flip-flop diseased nature.

Proof:
Let Nd denote nodes having dual nature, I.e which replicate into 2
Let Ns denote nodes having singular nature, I.e nodes which do not replicate at all

Let Kth level of tree has N1 dual nature nodes

So k+1 th level number of healthy nodes = 2*N1
but since the tree is diseased so
k+1 th level has nodes = ( 2*N1 – a1 ) + a1

where a1 is the nodes of nodes got diseased, So incapable of any further reproduction into duality

At level = k + 2
number of healthy nodes = 2 * ( 2N1 – a1 )
= 4*N1 – 2a1
but the tree is non-healthy so say b1 nodes again get diseased
so k+2 level nodes can be written as

k+2 has nodes = (4N1 – 2 a1 – b1 ) + b1
where b1 is the latest number of nodes to have got diseased, So incapable of any further reproduction into duality.

Extending the same logic at next level
At level = k + 3
number of healthy nodes = 2 * ( 4N1 – 2a1 – b1 )
= 8N1 – 4a1 -2b1

but the tree is non-healthy so, say, c1 nodes again get diseased
so k+3 level nodes can be written as
k + 3 has nodes = ( 8N1 – 4a1 – 2b1 – c1 ) + c1

Now let's take a break and find out how many leaf nodes and dual-nodes are present between Level=k and level=k+3

All the nodes at k+3 are leaf nodes
leaf nodes at level k+1 = a1
leaf nodes at level k+2 = b1
so total leaf nodes = 8N1 – 4a1 – 2b1 + a1 + b1
= 8N1 – 3a1 – b1

so Ns = 8N1 – 3a1 – b1

Now lets find out the total number of dual-nodes
level k+3 = 0
level k+2 = 4N1 – 2a1 – b1
level k+1 = 2N1 – a1
level k = N1

so total dual nodes = 7N1 – 3a1 – b1
so Nd = 7N1 – 3a1 – b1

Clearly Ns = Nd + 1

So number of leaf nodes is one greater than number of dual-nodes.

We stopped at level k + 3..... The same logic can be extended to fictitious infinite level binary tree

No comments:

Post a Comment