# CS301 Data Structures Assignment 4 Solution Fall 2013

Question 1(a):                                                                                                                                    Marks 2

Find the pre-order traversal of AVL tree given in solution of assignment 3.

Solution:

pre order:  40. 31.16 . 19 . 33 . 55 . 50. 52 . 68. 57 . 66. 77

Question 1(b):                                                                                                                                    Marks 8

Construct min heap from data traversed in question 1(a).

Solution:

Question 2(a):                                                                                                                                    Marks 2

Find the post-order traversal of AVL tree given in solution of assignment 3.

Solution: 19 . 16 . 33 . 31. 52 . 50 . 66 . 57 . 77 . 68 . 55 . 40 .

Question 2(b):                                                                                                                                    Marks 8

Construct max heap from data traversed in question 2(a).

Question 3:

An AVL tree is given in the solution file of assignment 3. Convert that AVL tree into a threaded binary tree and also use dummy node in this threaded binary tree.                                                                            Marks 5

Solution Guidelines:

1. Use assignment 3 solution file for AVL tree while finding pre-order, post-order traversal or constructing threaded binary tree.
2. In question 1(b) show final tree of min heap and status of array.
3. In question 2(b) show final tree of max heap and status of array.
4. While building max or min heap tree, read traversed values from left to right.

Solution 3: