The following definition of a TreeNode class will be used in the remainder of this section on building a binary tree.

public class TreeNode
{
  private Object value;
  private TreeNode left;
  private TreeNode right;

  public TreeNode( Object initValue, TreeNode initLeft, TreeNode initRight )
  {
    value = initValue;
    left = initLeft;
    right = initRight;
  }

  public Object getValue()
  {
    return value;
  }

  public TreeNode getLeft()
  {
    return left;
  }

  public TreeNode getRight()
  {
    return right;
  }

  public void setValue( Object theNewValue )
  {
    value = theNewValue;
  }

  public void setLeft( TreeNode theNewLeft )
  {
    left = theNewLeft;
  }

  public void setRight( TreeNode theNewRight )
  {
    right = theNewRight;
  }
}

Suppose the following integers were inserted into a sorted binary tree in the indicated order.

26  79  14  99  53  9  35  21  87

Draw the resulting binary tree.

Sorry, but your browser
doesn't support Java.

Animated Binary Tree Applet^*

You will notice that as each node was added to the tree, it was inserted as a leaf. The insert algorithm will be recursive.

Given this parameter list for the insert method, develop the pseudocode below it.

void insert (TreeNode node, Object data)
// Will insert data into an ordered binary tree. 
// The solution is recursive.