Binary Search Trees
Assignment 7
Submit your answers via Moodle. Submissions may be uploaded as PDF or as plain text files.
A LaTeX answer template is available here: answers.tex.
New to LaTeX? See the LaTeX guide for DSA students.
Exercise 1: Binary Search Tree Insertion (12 points)
Draw the BST that results when you insert the keys
E A S Y Q U E S T I O N, in that order
(associating the value i with the i-th key, as in the convention from the text),
into an initially empty tree. How many compares are needed to build the tree?
Exercise 2: Worst Cases (5 points)
Inserting the keys A X C S E R H into an initially empty BST gives a worst-case tree
where every node has one null link, except one at the bottom, which has two null links.
Give five other orderings of these keys that produce worst-case trees.
Exercise 3: Best Cases (5 points)
Give five orderings of the keys A X C S E R H that, when inserted into an initially empty BST,
produce the best-case tree.
Exercise 4: Tree Traversal (5 points)
- Give the preorder traversal of the given tree.
- Give the inorder traversal of the given tree.
- Give the postorder traversal of the given tree.
- What is the height of the given tree?
- What is the depth of node
7in the given tree?
Exercise 5: Perfect Balance (Creative Programming) (30 points)
Write a program that inserts a set of keys into an initially empty BST such that the tree produced is equivalent to binary search. In other words, the sequence of compares used to search for any key in the BST should be the same as the sequence of compares used by binary search for the same set of keys.