### SET 5

Question 1

**The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:**

A : 2^{h}-1

B : 2^{h-1}-1

C : 2^{h+1}-1

D : 2^{h+1}

Answer Discuss it!

.

Correct answer is :C

Solution :

Maximum number of nodes will be there for a complete tree.
Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + .... 2^h = 2^(h+1) - 1

Question 2

**The maximum number of binary trees that can be formed with three unlabeled nodes is:**

A : 1

B : 5

C : 4

D : 3

Answer Discuss it!

.

Correct answer is :B

Solution :

O
/
O O
(i)
O
/
O
/
O
(ii)
O
/
O
O
(iii)
O
O
O

Question 3

**The following postfix expression with single digit operands is evaluated using a stack:**

8 2 3 ^ / 2 3 * + 5 1 * -

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

A : 6,1

B : 5,7

C : 3,2

D : 1,5

Answer Discuss it!

.

Correct answer is :A

Question 4

**The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:**

A : d e b f g c a

B : e d b g f c a

C : e d b f g c a

D : d e f g b c a

Answer Discuss it!

.

Correct answer is :A

Solution :

Below is the given tree.
a
/
/
b c
/ /
/ /
d e f g

Question 5

**A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?**

A : 3

B : 4

C : 5

D : 6

Answer Discuss it!

.

Correct answer is :C

Solution :

For an n-ary tree where each node has n children or no children, following relation holds

L = (n-1)*I + 1

Where L is the number of leaf nodes and I is the number of internal nodes.

Let us find out the value of n for the given data.

L = 41 , I = 10

41 = 10*(n-1) + 1

(n-1) = 4

n = 5

Question 6

**Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:**

A : θ (logn)

B : θ (loglogn)

C : θ (n)

D : θ (n logn)

Answer Discuss it!

.

Correct answer is :B

Solution :

The height of a Max Heap is ?(logn). If we perform binary search for finding the correct position then we need to do ?(LogLogn) comparisons.

Question 7

**You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?**

A : O(log n)

B : O(n)

C : O(n log n)

D : none of the above, as the tree cannot be uniquely determined

Answer Discuss it!

.

Correct answer is :B

Question 1

.

Correct answer is :C

Solution :

Maximum number of nodes will be there for a complete tree. Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + .... 2^h = 2^(h+1) - 1

Question 2

.

Correct answer is :B

Solution :

O / O O (i) O / O / O (ii) O / O O (iii) O O O

Question 3

8 2 3 ^ / 2 3 * + 5 1 * -

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

.

Correct answer is :A

Question 4

.

Correct answer is :A

Solution :

Below is the given tree. a / / b c / / / / d e f g

Question 5

.

Correct answer is :C

Solution :

For an n-ary tree where each node has n children or no children, following relation holds

L = (n-1)*I + 1

Where L is the number of leaf nodes and I is the number of internal nodes.

Let us find out the value of n for the given data.

L = 41 , I = 10

41 = 10*(n-1) + 1

(n-1) = 4

n = 5

Question 6

.

Correct answer is :B

Solution :

The height of a Max Heap is ?(logn). If we perform binary search for finding the correct position then we need to do ?(LogLogn) comparisons.

Question 7

.

Correct answer is :B