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

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