### SET 4

Question 1

**What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.**

A : 2

B : 3

C : 4

D : 5

Answer Discuss it!

.

Correct answer is :B

Solution :

AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees

Question 2

**Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?**

A : 25,12,16,13,10,8,14

B : 25,14,13,16,10,8,12

C : 25,14,16,13,10,8,12

D : 25,14,12,13,10,8,16

Answer Discuss it!

.

Correct answer is :C

Solution :

A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data. In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.

Question 3

**Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on the correct answer to the previous question?**

A : 14,13,12,10,8

B : 14,12,13,8,10

C : 14,13,8,12,10

D : 14,13,12,8,10

Answer Discuss it!

.

Correct answer is :D

Solution :

For Heap trees, deletion of a node includes following two operations. 1) Replace the root with last element on the last level. 2) Starting from root, heapify the complete tree from top to bottom..
Let us delete the two nodes one by one:1) Deletion of 25:
Replace 25 with 12
12
/
/
14 16
/ /
/ /
13 10 8
Since heap property is violated for root (16 is greater than 12),
make 16 as root of the tree.
16
/
/
14 12
/ /
/ /
13 10 8
2) Deletion of 16:
Replace 16 with 8
8
/
/
14 12
/
/
13 10
Heapify from root to bottom.
14
/
/
8 12
/
/
13 10
14
/
/
13 12
/
/
8 10

Question 4

**In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?**

A : 0

B : 1

C : (n-1)/2

D : n-1

Answer Discuss it!

.

Correct answer is :A

Solution :

if a node has 1 child then it will be having even number of descendents which according to the question is not possible.

Question 1

.

Correct answer is :B

Solution :

AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees

Question 2

.

Correct answer is :C

Solution :

A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data. In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.

Question 3

.

Correct answer is :D

Solution :

For Heap trees, deletion of a node includes following two operations. 1) Replace the root with last element on the last level. 2) Starting from root, heapify the complete tree from top to bottom.. Let us delete the two nodes one by one:

1) Deletion of 25: Replace 25 with 12 12 / / 14 16 / / / / 13 10 8 Since heap property is violated for root (16 is greater than 12), make 16 as root of the tree. 16 / / 14 12 / / / / 13 10 8 2) Deletion of 16: Replace 16 with 8 8 / / 14 12 / / 13 10 Heapify from root to bottom. 14 / / 8 12 / / 13 10 14 / / 13 12 / / 8 10

Question 4

.

Correct answer is :A

Solution :

if a node has 1 child then it will be having even number of descendents which according to the question is not possible.