` CPS 100, Spring 2004 Recitation

CPS 100, Spring 2004 Recitation

Use the declaration for tree and list nodes given below for each of the questions.

struct ListNode { string name; ListNode * next; ListNode (const string & newName, ListNode * newNext) : name(newName), next(newNext) {} };

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

  1. Using the AVL tree created in the warmup, delete the element "p". Demonstrate any necessary rotations.
  2. Imagine that you are searching for the number 363 in a binary search tree. Which of the following could not have been the search sequence encountered and why?

    1. 121,234,456,352,363

    2. 919,553,213,311,363

    3. 161,741,140,159,363

  3. Write the function pathPrint that prints the values stored in every root-to-leaf path, with each path on one line and the root-value printed first. For example, for the tree below:
    tree

    the output should be 

     5 4 11 7
 5 4 11 2
 5 8 13
 5 8 4 1
    You should write a function with the header below, but you may want to write another function that pathPrint calls. For example, a helper function may take a tree and a vector or stack. The invariant of the auxiliary data structure is that it stores the values on the path from the root to the node last visited (initially the vector is empty). When reaching null (past a leaf) the vector can be printed representing a root-to-leaf path.

    Assume trees store int values.

    void pathPrint(Tree * t) // post: all root-to-leaf paths printed, one path per line
  4. Write a recursive function Tree2ListRec that traverses a binary search tree in order and adds each name to a data structure of your choosing. Try using a stack and then a queue for this purpose.

    Complete the function Tree2ListRecS and Tree2ListRecQ below.

    void Tree2ListRecQ(TreeNode * t, ________________________ q) // precondition: t is the root of a binary search tree // postcondition: q contains the names in t in sorted order { if (t != NULL) { Tree2ListRecQ(t->left, q); _____________________________ Tree2ListRecQ(t->right, q); } } void Tree2ListRecS(TreeNode * t, ________________________ s) // precondition: t is the root of a binary search tree // postcondition: s contains the names in t in reverse sorted order { if (t != NULL) { Tree2ListRecS(t->left, s); _____________________________ Tree2ListRecS(t->right, s); } }
  5. Write functions, Tree2ListQ that uses Tree2ListRecQ and Tree2ListS that uses Tree2ListRecS, the resulting data structures to build a sorted linked list. You may assume that Tree2ListRecQ and Tree2ListRecS from the previous section work correctly even if your implementations do not.

    Complete the functions, Tree2ListS and Tree2ListQ below.

    ListNode * Tree2ListS(TreeNode * t) // precondition: t is the root of a binary search tree // postcondition: returns a pointer to the first node of a // sorted linked list containing same values as t { ListNode * result = 0; if (t!=0) { ____________ s; Tree2ListRecS(t, s); } return result; } ListNode * Tree2ListQ(TreeNode * t) // precondition: t is the root of a binary search tree // postcondition: returns a pointer to the first node of a // sorted linked list containing same values as t { ListNode * result = 0; if (t!=0) { ____________ q; Tree2ListRecQ(t, q); } return result; }
  6. Describe how you could write the functions Tree2ListRec and Tree2List, so that they built the list directly, without using an extra data structure
  7. Write the recurrence and resulting big-Oh for the above function.
Jeff Forbes
Last modified: Sat Feb 21 01:10:16 EST 2004