Short Assignment 7
Due: Monday, February 1

I mentioned in class that parent pointers are necessary to do things like determining the depth of a node in a tree, among other things. The first thing that you will do in this short assignment is to add a fourth instance variable called parent to our BinaryTree class. The parent should refer to the parent of the current node, and should be null for the root of the tree. You should also add a method getParent that returns a reference to the parent of a tree node, or null if the node is the root.

How should the parent pointers get set? Clearly the constructors will have to be changed to initialize it. You might think that we would want a setParent method, but this can cause problems. If you set a parent value without setting the corresponding left or right in the parent to point to the child you can create an inconsistent tree. It is better to have constructors always initialize parent to null and make setLeft and setRight responsible for setting the parent pointer of the child (unless the child is null), as well as the left or right in the parent node. Similarly, the three-parameter constructor should set the parent pointers of the two children as well as the left and right of the current node. This reduces the probability that the tree will be inconsistent. (You can guarantee consistency if you require that the parent, left, and right values are null when the constructor, setLeft, or setRight sets them. However, this removes the option of re-structuring the tree, which we will see can be useful for things like deleting nodes. Therefore we do not do it.)

The second part of this assignment is to add four new methods to the BinaryTree class. I've started them for you in BinaryTree.java. Download that file, along with MutableInteger.java.

The MutableInteger class is like the Integer wrapper class, but it includes methods set and get; the Integer class has no setter method. On the other hand, because I had to write MutableInteger and it's not built into the Java language, autoboxing and unboxing do not apply to this class. You will not need to make any changes to the MutableInteger class.

In BinaryTree.java, you will see headers for four new methods whose bodies you have to write:

• isRoot returns a boolean indicating whether the node is the root of the entire tree.
• depth returns the depth of the node, which is the number of edges in the unique path from this node to the root of the entire tree. For example, the depth of the root is 0, the depth of the children of the root is 1, the depth of the grandchildren of the root is 2, and so on.
• countLeaves returns the number of leaves in the subtree rooted at the node.
• copy makes a copy of the subtree rooted at the node, returning a reference to the root of the copy of the subtree.

Your isRoot should take constant time, and depth should take time Θ(d), where d is the depth of the node. You may write the depth method either iteratively (i.e., using a loop) or recursively. (Using recursion and the ternary operator, I was able to write the body of depth in one line, but you are not required to do so.)

You must write both countLeaves and copy recursively. (This is a favor to you - writing them non-recursively is much harder.) For countLeaves, you may not call fringe, although you may look to it for inspiration.

The copy method makes what we call a shallow copy. You should make a copy of each node, but do not make a copy of the object that the data instance variable references. You should work directly with the nodes; you are specifically prohibited from calling reconstructTree as part of the copy method. (And no fair doing something like making a new method that is exactly like reconstructTree but with a different name and calling it from within copy. You must work directly with the nodes.) Because it's a shallow copy, the value of data in a node and in its copy should be aliases. Therefore, if you call setValue on the copy of a node, the node and its copy will reference different objects in their data instance variables, because you've changed the reference in data within just the copy. But if you change the instance variables in the object that data references in the copy of a node, both the original node and the copy will still reference the same object in their data instance variables, but that referenced object will have changed.

I have updated the main method in BinaryTree.java to exercise the new methods that you will write. Here's what the output should look like:

tree: 
  7
    5
3
    1
      6
  2
    4

Size of tree = 7
Height of tree = 3
Fringe of tree = [4, 6, 5]
Number of leaves = 3
Depth of node 1 = 2
Preorder traversal of the tree = [3, 2, 4, 1, 6, 7, 5]
Inorder traversal of the tree = [4, 2, 6, 1, 3, 5, 7]
Postorder traversal of the tree = [4, 6, 1, 2, 5, 7, 3]
tree1: 
  7
    5
3
    1
      6
  2
    4

tree and tree1 are equal? true
tree: 
  7
    5
3
    1
      6
  2
    4

modified tree1: 
  8
    5
3
    1
      6
  2
    4

tree and tree1 are equal? false
tree2: 
  7
    5
3
    1
      6
  2

Size of tree2 = 6
Height of tree2 = 3
Fringe of tree2 = [6, 5]
tree and tree2 are equal? false
tree3: 
  7
    5
3
    1
      6
  2
    4

Size of tree3 = 7
Height of tree3 = 3
Fringe of tree3 = [4, 6, 5]
Number of leaves = 3
Depth of node 1 = 2
tree and tree3 are equal? true
tree's right child's value = 8
tree3's right child's value = 8

Note that the last three lines of main,

  tree3.getRight().getValue().set(8);
  System.out.println("tree's right child's value = " + tree.getRight().getValue());
  System.out.println("tree3's right child's value = " + tree3.getRight().getValue());

should show that in both the original tree and tree3, the right child of the root references the same MutableInteger object.

Submit your updated BinaryTree.java file and the console output via Canvas. (Yes, the console output should match the above exactly, but submit it anyway, to show that you've tested your code.)