## CPSC 220 Fall 2005

HW 12: Computing Height and Balance in Trees

As we discussed briefly in class, one way to represent a binary tree defines a class
to represent each node in the tree. This is analogous to the way a linked list is
represented, but with each node referring to two additional nodes (the left and right
children) instead of just one:
Consider the class BTNode below:

public class BTNode{
protected Object element; // Value stored in this node
protected BTNode left; // Reference to left child
protected BTNode right; // Reference to right child
public BTNode(Object value)
{
this.element = value;
left = null;
right = null;
}
public BTNode(Object value, BTNode left, BTNode right)
{
this.element = value;
this.left = left;
this.right = right;
}
}

(This is similar to the BinaryTreeNode class on p. 176 of L&C, but BTNode provides
an additional constructor and does not include the numChildren method.)
This defines a BTNode as an object that contains an element and a reference
to two additional BTNodes, the left and right children.
One can construct a BTNode by providing just
the element, in which case the left and right children are set to null, or one can provide the
element plus the left and right children when the node is constructed. Note that the children
need to be BTNodes themselves, and that there must be an element -- there is no such
thing as an "empty" BTNode.

Note that we haven't actually defined a BinaryTree class, but we can still work with
the tree structure by manipulating BTNode objects. We did this last semester
with lists as well;
we used the LinearNode class to define various list classes (List, SortedList, etc), but
informally sometimes we just worked with LinearNode objects directly. Our BTNode class does
not currently have methods equivalent to getNext and setNext in the LinearNode class, so
a tree must be built by constructing nodes from other nodes. For example,
the code below produces the tree shown:

BTNode A = new BTNode("A");
BTNode B = new BTNode("B");
BTNode C = new BTNode("C", A, B);
BTNode D = new BTNode("D", null, C);
D
\
C
/ \
A B

Your assignment:

- Write a method
*int height()* for the BTNode class that returns the height
of the current node. By our convention the height of a node is the
longest path from that node to a leaf, so a node with no children has height 0.

- Write a method
*int balance()* for the BTNode class that returns the
balance factor of the current node.

- Write a driver that uses BTNodes to construct the following tree, then
uses the methods above to find the height and balance factor for each node. Embed
print statements as necessary to print these values; be sure you print the labels on the
nodes as well.
A
/ \
B C
/ \ \
D E F
/ \
G H
\
I