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

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.

a) log

_{2}*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.
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.

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 + ........... +n

_{m}
Equation 5 can be generalised to

n0 = n2 + 2n3 + 3n4 + ......... + (m-1)n

_{m}+ 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,.........................n

_{m-1}= 0 as there are only nodes having degree 0 or m
n0 = 0 + 0 + 0 +.............. (m-1)n

_{m}+ 1
n0 = (m-1)n

_{m}+ 1
we know that n = n0 + n1 + n2 + n3 + ........... +n

_{m}
n = ((m-1)n

_{m}+ 1) + 0 + 0 +..................................+ n_{m}
n = m*n

_{m}+ 1
n

_{m}= (n - 1) / m
then n0 = (m-1)n

_{m}+ 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!!!

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