Binary Tree Example
CIT 594, Spring 2005

The BinaryTree API

Your Binary Tree Assignment asks you to implement an API (Application Programmer's Interface) for a Binary Tree ADT (Abstract Data Type). Here is what you are giving the application programmer to work with:

Constructors:

Methods:

Notice that the IllegalArgumentException that could be thrown by a couple of these methods is a RuntimeException, which means that the user does not need to wrap every call to these methods with try...catch.

The program

Suppose I wanted to use your BinaryTree class to sort an array of numbers. I can do this by putting the numbers into a sorted binary tree--a tree in which each node contains a number, all the numbers in the left subtree of a node are smaller than the number in the node, and all the numbers in the right subtree of a node are larger than or equal to the number in the node. Like this:

Here's what I need to do:

  1. Create a root node containing some number (I don't care which one) from the array.
  2. For each remaining number, insert it into the binary tree, keeping the tree sorted. (This is a recursive search to find the right place to put the number.)
  3. Traverse the binary tree in inorder (left subtree, root, right subtree), copying each number back into the array.

Notice that the tree in the picture above happens to be nicely balanced. It's a lot of work to keep a tree balanced, and I have no reason to do so. So I won't.

Here's my code:

import java.util.Arrays;
import java.util.Random;

/**
 * A simple demonstration of the use of the BinaryTree API.
 * @author David Matuszek
 */
public class BinaryTreeSort {
    /**
     * Creates and executes an instance of this class.
     * @param args Unused.
     */
    public static void main(String[] args) {
        new BinaryTreeSort().sortDemo();
    }
    /**
     * Demonstrates the use of a binary tree to perform a sort.
     */
    private void sortDemo() {
        int[] array;
        
        array = makeRandomArray();
        System.out.println("Random array: " +
                           Arrays.toString(array));
        sort(array);
        System.out.println("Sorted array: " +
                           Arrays.toString(array));
    }
    /**
     * Sorts an array.
     * @param array The array to be sorted.
     */
    private void sort(int[] array) {
        // Create root of tree with first number in array
        BinaryTree<Integer> tree = new BinaryTree<Integer>(array[0]);
        // Put the rest of the numbers into the binary tree
        for (int i = 1; i < array.length; i++) {
            insertNumberIntoTree(array[i], tree);
        }
        // Get the numbers back out (sorted)
        copyTreeIntoArray(tree, array);
    }
    /**
     * Do an inorder walk of the tree to get the numbers
     * out in sorted order.
     * @param tree The sorted tree of numbers.
     * @param array The location in which to put the numbers.
     */
    private void copyTreeIntoArray(BinaryTree<Integer> tree,
                                   int[] array) {
        // This is just a facade method, so that the user does not
        // have to supply an extra zero argument
        copyTreeIntoArray(tree, array, 0);
    }
    /**
     * Copies a binary tree into an array, in inorder.
     * @param tree The tree to copy.
     * @param array The array to get the values.
     * @param i The next location in the array to receive a value.
     */
    private int copyTreeIntoArray(BinaryTree<Integer> tree,
                                  int[] array,
                                  int i) {
        // Note: The hard part was setting "i" to the correct value
        if (tree == null) return i;
        i = copyTreeIntoArray(tree.getLeftChild(), array, i);
        array[i] = tree.getValue();
        i = copyTreeIntoArray(tree.getRightChild(), array, i + 1);
        return i;
    }
    /**
     * Puts the given number into the tree in the proper place
     * to keep the tree sorted.
     * @param n The number to put int the sorted binary tree.
     * @param tree The binary tree to receive the number.
     */
    private void insertNumberIntoTree(int n,
                                      BinaryTree<Integer> tree) {        
        // Smaller numbers go to the left
        if (n < tree.getValue()) {
            if (tree.getLeftChild() == null) { // base case
                tree.setLeftChild(new BinaryTree<Integer>(n));
            } else { // recursive case
                insertNumberIntoTree(n, tree.getLeftChild());
            }
        }
        // Larger and equal numbers go to the right
        else if (tree.getRightChild() == null) { // base case
            tree.setRightChild(new BinaryTree<Integer>(n));
        } else { // recursive case
            insertNumberIntoTree(n, tree.getRightChild());
        }
    }
    /**
     * Creates a random array of 12 two-digit numbers.
     * @return The array of random numbers.
     */
    private int[] makeRandomArray() {
        Random rand = new Random();
        int[] result = new int[12];
        for (int i = 0; i < result.length; i++) {
            result[i] = rand.nextInt(89) + 10;
        }
        return result;
    }
}