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

                                          1999 APCS AB Exam: Question 4

Consider a binary tree of names. Names may appear more than once in the tree as shown in the example below.

   Assume that a binary tree of names is implemented using the
     following declaration.

           struct TreeNode
           {
             apstring name;
             TreeNode * left;
             TreeNode * right;
           };

     Assume that the integer function Max has been defined. Max
     returns the greater of its two integer parameters, as specified
     below.

           int Max(int x, int y)
           // postcondition: returns the maximum of x and y

     A path in a tree is a sequence of nodes

          node1, node2, ... nodek

     such that for any j, nodej + 1 is either the left child or right
     child of nodej. The length of a path is the number of nodes in
     the path (k in the example just given).

       a. Write function PathLength, as started below. If person P is
          in tree T, then PathLength(T, P, 1) should return the length
          of the longest path from the root of T to a node containing
          P; if person P does not appear in tree T, then PathLength(T,
          P, 1) should return 0. Note that parameter level can be used
          to keep track of the current level of the tree.

          For the tree given above, the following are examples of
          calls to PathLength.

          Function Call                         Value Returned
          PathLength(T, "Susan", 1)                    4
          PathLength(T, "Ken", 1)                      3
          PathLength(T, "Chris", 1)                    6
          PathLength(T, "David", 1)                    0
          PathLength(T->left, "Theresa", 1)            1
          PathLength(T->right->left, "Don", 1)         3

          In writing PathLength, you may call function Max as
          specified in the beginning of this question. Assume that Max
          works as specified.

          Complete function PathLength below.

          int PathLength(TreeNode * T, const apstring & someName, int level)

       b. Write function RootPath, as started below. RootPath should
          return the length of the longest path from the root of the
          tree to a node containing the same name as the root; if no
          node other than the root contains that name, then RootPath
          returns 1; if the tree is empty, RootPath should return 0.
          For the tree given above, the following are examples of
          calls to RootPath.

          Function Call                  Value Returned
          RootPath(T)                           4
          RootPath(T->left)                     1
          RootPath(T->right)                    5
          RootPath(T->left->left->left)         0

          In writing RootPath, you may call function PathLength
          specified in part (a). Assume that PathLength works as
          specified, regardless of what you wrote in part (a).

          Complete function RootPath below.

                int RootPath(TreeNode * T)