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.)