Data Structures

Data Structure multiple choice questions here...

Operating Systems

Operating Systems multiple choice questions here...

Sunday, April 28, 2013

Tree height

The maximum number of nodes in a ternary tree with height h

a. (3^(h + 1) - 1 )/ 3          b. (3^h - 1) / 2         c. (3^h - 1 ) /  3           d. (3^(h + 1) - 1)/ 2


The answer is d. (3^(h + 1) - 1) /2

Ternary tree is like a binary tree where each node can have a maximum of 3 children.

At height 0 there is one node, at height 1 there are 3 nodes, at height 2 there are 3^2 nodes and the sequence goes on,

1, 3, 3^2, 3^3,.........................................3^h

if we solve this geometric progression, the answer will be (3^(h + 1) - 1) / (3 - 1)  = ( 3^(h + 1) - 1) / 2



The maximum number of nodes in an 'm' ary tree with height h, where each node in the tree can have a maximum of m children is (m^(h+1) - 1) / (m - 1). 

Suppose m=2 i.e. a binary tree, then maximum number of nodes in a binary tree of height h is (2^(h+1) - 1) / (2 - 1) = 2^(h+1) - 1.


Note: m^h is "m to the power of h"  i.e 6^3=6 * 6* 6. 


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

Number of ordered binary trees

The no of possible ordered binary trees with 5 nodes A, B, C, D, E is

a. 15               b. 9               c. 41           d. 42


The answer is  d. 42

The number of possible ordered binary trees is given by the formula :
1/n+1 (2n C n)
Here n is 5, 1/n+1 (2n C n) = 1/6 (10 C 5) = 42.

The formula 1/n+1 (2n C n) is bit more complex. The derivation of the formula we shall discuss in one of the future posts.

Note: nCr = n! / (r! * (n-r)!)

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