CS301 Data Structure Assignments No.3 Solution and Discussion Fall 2014 Due Date: July 01, 2014

Assignment No. 03(Non-Graded)
SEMESTER Spring 2014
CS301- Data Structures


Total Marks: 20



Due Date: 01/07/2014
Instructions

Please read the following instructions carefully before solving & submitting assignment:

It should be clear that your assignment will not get any credit (zero marks) if:

The assignment is submitted after due date.
The submitted assignment file is other than .doc or .docx format.
The submitted assignment file does not open or corrupted.
The assignment is copied (from other student or ditto copy from handouts or internet).


Uploading instructions

For clarity and simplicity, You are required to Upload/Submit only one .doc file.

Don’t wait for grace day. Grace Day is given only if there is problem with LMS on due date. Submit your solution within due date.
Note that no assignment will be accepted through email if there is any problem on grace day.


Note: Use only MS Word.



Objective

The objective of this assignment is to make you familiar with the concepts of BST, Traversals and AVL tree.



For any query about the assignment, contact at cs301@vu.edu.pk



GOOD LUCK

Marks: 20 




AVL tree is a self balancing tree. If we have ordered data, BST built from is like a Linked List. AVL tree provides the solution for this situation.



You are required to traverse the above given BST using inorder traversal and build AVL tree for resulted data.





Programming Practice Task:



Binary search trees are constructed in such a way that the values less than root go to the left of the root and greater values reside on right side. You are required to write a program for the BST construction. The program should contain the tree class, insertion function, populate tree function and traversal functions. Pass the values from main to the populate tree function.



Populate tree function pass the values obtained from the main to insert method and insert will actually embed these nodes to the tree.



Also write the display function for the tree. In display function, call the all three (inorder, preorder, postorder) traversal functions.

Sample Output:

Note: Do not send the code file along with solution file as it’s just for practicing the BST code. The code will be discussed in TDB session.



Solution Guidelines:



In first part of assignment, perform the inorder traversal on given BST.
From the data obtained from the traversal build AVL tree.




Note: You are required to Upload/Submit only one .doc file. Do not submit the code file as Programming Practice Task is given only for the practice. The solution of the practice question will be discussed in Team Discussion Board session.




Lectures Covered:  This assignment covers Lecture # 19-23.

Deadline:           Your assignment must be uploaded / submitted on / before, July 01, 2014.