In addition to all concepts from Quiz 1, Quiz 2, and Quiz 3,

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, path, depth of a node, subtree, height of a tree, height of a node
• Tree traversals: pre-order, in-order, post-order, and level-order traversals
• Binary tree
• Binary search trees and the BST property
• The dictionary interface
• AVL trees and the AVL tree property
• Tree rotations
• The recursive definition of binary trees, binary search trees, and AVL trees

You should be familiar with the following C++-related concepts:

• Iterators
• assert
• Command-line arguments
• Basic uses of file streams

Practice problems

1. 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. Draw the tree obtained by inserting 10 into the tree.
   6. Draw the tree obtained by deleting 2 from the tree.
   7. Draw both trees that might be obtained by deleting 4 from the tree.
2. 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:

     template <typename K, typename V>
     bool LinkedBst<K,V>::containsInRange(K min, K max) {
       return subtreeContainsInRange(root, min, max);
     }
   

   Write the recursive helper function subtreeContainsInRange. You may assume that empty trees are represented by pointer to a NULL node.
3. For each of the code fragments below, draw the AvlTree that results from the code fragment:

   1.   AvlTree<int,int> t;
        for (int i = 1; i <= 10; ++i) {
          t.insert(i,i);
        }
      

   2.   AvlTree<int,int> t;
        for (int i = 1; i <= 5; ++i) {
          t.insert(i,i);
          t.insert(-1*i,-1*i);
        }
      

   3.   AvlTree<int,int> t;
        for (int i = 1; i <= 5; ++i) {
          t.insert(i,i);
          t.insert(11-i,11-i);
        }
      

4. For each of the three code fragments above, draw the tree that would result if a LinkedBst were used instead of an AvlTree.
5. What is the worst-case running time of the following function? Use Big-O notation.

     void f(int n) {
       if (n < 0) {
         return;
       }
       AvlTree<int,int> t;
       for (int i = 0; i < n; ++i) {
         t.insert(i,i);
       }
       for (int i = 0; i < n; ++i) {
         cout << t.remove(i) << endl;
       }
     }
   

6. What is the smallest AVL tree such that removing a node requires a rotation to rebalance the tree? (There is more than one correct answer, but they're all the same size.)
7. What is the smallest AVL tree such that removing a node requires two rotations to rebalance the tree? (Again there is more than one correct answer, but they're all the same size.)

Home Page