### Data Structures

Data Structure multiple choice questions here...

### Operating Systems

Operating Systems multiple choice questions here...

## Sunday, April 28, 2013

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

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