This homework is about trees.

[20 points] Do the following problems from the G&T text book (pgs. 194-195):

R-5.1

R-5.7

R-5.10

R-5-11 (your tree need only be of height 5 for parts 1 and 2; ignore the spurious k in part 6)

[30 points] Implement a binary tree datatype in Java. A tree node should contain an integer identifier (ID) and, for internal nodes, left and right children. Additionally, all nodes should contain a parent pointer. Clearly define what constitutes a leaf (i.e., external) node before you begin.

To test your tree datatype, construct a loop that reads characters from a string. The program should recognize three characters that have the following interpretation:

'l': descend left from the current node. If the left child of the current node does not exist, create it and set it as the current node.

'r': descend right from the current node. If the right child of the current node does not exist, create it and set it as the current node.

'u': move to the parent of the current node. Handle the case when the current node is the root.

After every operation, print the ID of the current node; node creation should increment the node ID. You may also want to log all operations such as movement in the tree, etc. For example, the string "llurur" might print:

    At node #0
    Created left leaf with ID #1 for node #0
    Created left leaf with ID #2 for node #1
    Moved up to node #1
    Created right leaf with ID #3 for node #1
    Moved up to node #1
    Moved right to node #3

You may intially create a single root node to get the process started. Pass the string to interpret as args[0] to main.

The DrawTree applet of lab 7 may be useful in verifying that your trees are correctly constructed.

Hand in: answers to Part I; code and scripts for Part II. Be sure to include documentary comments in your code.
instructions on how to submit