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
```

CPSC 220 Fall 2005HW 12: Computing Height and Balance in Trees

CPSC 220 Fall 2005
HW 12: Computing Height and Balance in Trees