COP 3530, Discrete Data Structures and Algorithms, Summer 1999, Homework 6 :: UFL Florida Computer Programming Homework

Class Notes: Data Structures and Algorithms Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344 Homework #6 -- Due Fri 09 July 1999 : 09.30am In class, we discussed AVL trees, binary search trees, and the breadth-first and depth-first search (BFS and DFS) algorithms for graph or tree traversal. The purpose of this homework is to exercise your knowledge and develop skills you will need for the exams and for Projects 4 and 5. Use your class notes and the text (Chapter 12) as a guide to answering the following questions. Clarifications in response to student questions are posted in red typeface. * Question 1. Given the sequence {-3, 8, 2, -1, 4, 6, -2, 10}, (a) [1 point] Diagram an unbalanced binary search tree (BST) for this sequence. Right and left subtrees of the root should differ by two levels. This means that the balance factor can be -2 or +2. (b) [1 point] Traverse the BST using DFS and label the vertices by their values as they are encountered, as you did for Homework #5. (c) [1 point] Repeat Question 1b), but for BFS instead of DFS. (d) [1 point] Tell which method - DFS or BFS - would be better for outputting the BST values in sorted order. You do not have to start at the root of the tree. To get credit, you must explain your answer in 1-2 sentences. * Question 2. Given the sequence S = {-9, 2, 4, 6, 30, -10, 1, 5, 8, 7}, (a) [1 point] Diagram a binary search tree (BST) for this sequence. (b) [1 point] Insert the values -46, -47, 38, 39, 40, and 45 into the BST you diagrammed in Question 2a) and draw the new BST (the resultant tree, after all values are inserted). (c) [1 point] Using the array representation of a binary tree that we discussed in class, diagram the array representation of the tree you obtained in Question 2a).