MCX2                                                                                                                 Math Department
Mr. Gary. Jaye                                                                                                    Danny Jaye, A.P.S.

                                          1997 APCS AB Exam: Question 3

Assume that binary trees are implemented using the following declarations 

    struct Tree
    {
        int info;
        Tree * left;
        Tree * right;

        // provide constructor
        Tree(int val, Tree * lchild = 0, Tree * rchild = 0)
           : info(val),
             left(lchild),
             right(rchild)
        { }
    };

Part A 
Write function CountNum whose header is given below. CountNum returns the
number of nodes in tree T that contain the value key. 

For example, if T is as pictured below, CountNum(T,0) returns 2,
CountNum(T,1) returns 3, and CountNum(T,2) returns 0. 

Complete function CountNum below the following header 

int CountNum(Tree * T, int key)
// precondition: returns the number of nodes in Tree T    
//               with the value key.  Returns 0 if no
//               nodes contain key or if the tree is empty    

Part B 
Write function Insert whose header is given below. Insert creates a new node
containing the value key and inserts this new node between the node pointed
to by P and either P's right child (if the direction is 'R') or P's left
child (if the direction is 'L'). If direction is 'R', the right child of P
becomes the right child of the new node and the new node becomes the right
child of P. If direction is 'L', the left child of P becomes the left child
of the new node and the new node becomes the left child of P. 

For example 

                                                  
Complete function Insert below the following header. Assume that Insert is
called only with parameters that satisfy its precondition. 

void Insert(Tree * p, int key, char direction)
// precondition: P is not NULL/0.  If direction is 'R',
//               P has a right child; if direction is 'L',
//               P has a left child.
// postcondition: If direction is 'R', a node containing the    
//                value key is created and inserted between P and
//                P's right child.
//                If direction is 'L', a node containing the    
//                value key is created and inserted between P and
//                P's left child.

Part C 
Write function Separate, whose header is given below. Separate modifies tree
T in the following way: for each occurrence of a parent and child that contain
the same value n, a new node is inserted between them containing the value n-1. 

For example: 

In writing Separate you may call the function Insert of part (b). Assume
that Insert works as specified, regardless of what you wrote in part (b). 

   void Separate(Tree * t)