CPS 100, Fall 2002, Week #7

Answer the following questions and bring them to your recitation on Oct 28-30, 2002.

Here are some declarations.

struct TreeNode { string info; TreeNode * left, * right; TreeNode(const string& s, TreeNode * lptr, TreeNode * rptr) : info(s), left(lptr), right(rptr) { } };

  1. Write the function treeToVector that converts a search tree into a sorted vector. For example, if root points to to the root (melon) of this tree:
             
                    melon
                    /    \
                   /      \
                grape     pear
                /   \         \
               /     \         \
             apple   lemon    tangerine
    
    the call
       tvector vec;
       treeToVector(root, vec);
    
    
    will return a vector represented by the following
      ("apple", "grape", "lemon", "melon", "pear", "tangerine")
    
    This function should be recursive and use push_back to insert into the vector.
    void treeToVector(TreeNode * tree, tvector & vec)
    {
    
    
    
    
    
    
    
    }
    
    
  2. Write a recurrence relation for treeToVector assuming that the tree passed in (and all subtrees) are roughly balanced (so each subtree contains roughly half as many nodes as the entire tree). The recurrence should include the base case/empty tree, and a non-empty tree. Let T(n) be the time for treeToVector to execute on an n-node tree, then:
    
    
    
     T(n) = 
    
     T(0) = O(1)
    
    

  3. Write the function IsBalanced whose header is below. IsBalanced returns true if its tree parameter is height balanced. For every node in the tree, the height of its left and right subtrees differ by no more than one.

    You may assume the function height exists and it runs in O(N) time on a tree with N nodes.

    int height(Tree * t); //returns height of tree // returns 0 if tree is NULL, 1 if tree has one node.

    The function isBalanced should be recursive and should call the height function above.

    bool isBalanced(Tree * t) { }

Susan H. Rodger
Last modified: Wed Oct 23 16:26:16 EDT 2002