Warning: This is a preliminary version, more exercises will be added soon, so come back to this page soon!.

In addition to all concepts from Test 1, and Test 2

You should be able to define or explain the following terms:

• Trees and many related terms and properties, including nodes, the root node, leaf nodes, parent, child, subtree, height of a tree
• Compare and contrast linear data structures with trees
• Binary tree
• Tree traversals: pre-order, in-order, post-order, and level-order traversals
• Binary search trees and the BST property
• Dictionary ADT
• STL implementation of dictionaries (very generally)
• Run time analysis of public interface for Binary Search Trees

Practice problems

1. For each data structure covered in the course, come up with a real-world application that motivates the data structure. The data structure should be able to provide a more efficient solution to the problem then any other structure covered so far.


2. (hard) Give a binary tree with integer keys at nodes, whose traversals are:
   • PreOrder: [80 46 92 90 121 111 105]
   • InOrder: [46 80 90 92 105 111 121]
   • PostOrder: [46 90 105 111 121 92 80]
   Is the tree a BST? Justify your response.


3. Consider the following tree:
   
   1. What is the pre-order traversal of the tree?
   2. What is the in-order traversal of the tree?
   3. What is the post-order traversal of the tree?
   4. What is the level-order traversal of the tree?
   5. Identify if it is a tree, binary tree, binary search tree
   6. Based on your previous answer, draw the tree obtained by inserting 10 into the tree.
   7. Draw the tree obtained by deleting 2 from the tree.
   8. Draw both trees that might be obtained by deleting 4


4. Using the IntBST representation you saw in class, describe the sequence of recursive calls made by the fourth insert function in the code below.

   int main() {
   IntBST *dict = new IntBST();
     dict->insert(5, 5);
     dict->insert(9, 9);
     dict->insert(11, 11);
   
     // trace through the following function
     dict->insert(10, 10);
   
     cout << "goodbye!" << endl;
   }
   

5. Consider a boolean function LinkedBST::containsInRange that takes as arguments two keys -- min and max -- and returns true if there exists a key k in the tree such that min <= k <= max. One possible implementation of this function is to call a recursive helper function that takes an additional argument -- a node in the tree, and returns whether that subtree contains any keys in the range:

   bool IntBST::containsInRange(int min, int max) {
      return containsInRange_h(root, min, max);
   }
   

   Write the recursive helper function containsInRange_h. You may assume that empty trees are represented by pointer to a NULL node.

Home Page