Wednesday, June 26, 2013

Ternary tree leaf nodes

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

a) n/2      b) (n-1)/3  c) (n-1)/2  d) (2n+1)/3


The answer is: d) (2n+1) / 3

Let us derive the answer assuming the ternary tree a full ternary tree

The maximum number of nodes in a ternary tree with height h is (3^(h + 1) - 1) / 2

(3^(h + 1) - 1) /2  = n
(3^(h + 1) - 1)  = 2n
3^(h + 1)  = 2n + 1
3^h * 3 = 2n+1
3^h = (2n+1) /3

At level h i.e. the number of leaf nodes in a ternary tree is 3^h.

So the number of leaf nodes in a ternary tree of n nodes is (2n+1)/3

 

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

The maximum number of nodes in an m'ary tree with height h is (m^(h+1) - 1) / (m - 1). 

(m^(h + 1) - 1) / (m-1)  = n
(m^(h + 1) - 1) = n(m-1)
m^(h + 1) = n(m-1) + 1

m^h *m = n(m-1) + 1
m^h = (n(m-1) + 1) / m
m^h = (nm - n + 1) / m

At level h i.e. the number of leaf nodes in an m'ary tree is m^h.

So the number of leaf nodes in an m'ary tree of n nodes is (nm - n + 1) / m.

Suppose m=2 i.e. a binary tree, the number of leaf nodes in a binary tree of n nodes is (2n - n + 1) / 2 = (n+1)/2.


Actual proof is not this straight forward. Let us consider a ternary tree which is not a full ternary tree but has either 0 or 3 children.
Here the number of nodes on level 0 is 1, on level 2 is 3, on level 3 is 6.  The number of leaf nodes are 7 i.e. on level 1 there is one leaf node and on level 2 there are 6 leaf nodes.

According to the formula the number of leaf nodes is (2n+1)/3.
Here n= 10
(2n+1)3 = (2*10+1)/3 = 21/ 3 = 7 which is the right answer, so how is it possible? A detailed proof is given here.

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

3 comments:

  1. I was recommended this website by my cousin. I'm now not positive whether or not this put up is written via him as no one else realize such certain approximately my difficulty. You're incredible! Thanks! yahoo sign in

    ReplyDelete
  2. I read your post and got it quite informative. I couldn't find any knowledge on this matter prior to. I would like to thanks for sharing this article here. Cept Coaching Classes.

    ReplyDelete