Storing The Data

Start At The Beginning

As with linked lists, you must always consider the various possible scenarios when you are adding data to a Binary Search Tree (BST). However, unlike linked lists, there are really only two concerns: 1) If the tree is empty, and 2) Otherwise. Again, not seriously complicated.

If the tree is empty (i.e., the root reference is null), you simply assign the node to the root reference as shown here.

   // check for empty tree
   if( rootRef == null )
      {
       rootRef = new BST_NodeClass( data );
      }

Adding A Node

There are two fundamental ways to add nodes to a tree after the first node has been added. The first might be to "look down" from a given node, see if child reference below is null and add the node to the child reference. On the other hand, if the child reference below is not null, then the operation must recursively track that reference down to the next node which will again look down, and so on. Again, recursion makes this operation pretty straightforward, as shown here.

   // inside add/insert method

   // check if search value is less than local data
       {
        // check if left child does not exist
           {
            // assign the current node's left child
            // to a new node with the given data

        // otherwise, assume left child does exist
           {
            // call the method recursively to the left
           }
   *
   *
   *

The other way to add data to a tree is to create each node and then return the node's reference to essentially link the data into the tree from the point where the recursion has found a null. This is as opposed to the other process where the recursion will never get to a null location because the method above will check for the null before it moves downward. Consider the following code.

   // inside add/insert method

   // check if the current node is not null
       {
        // check if new data is less than the current node data
           {
            // recurse to the left,
            // assigning the result to the current left child
           }

        // otherwise, assume the data is to the right
           {
            // recurse to the right,
            // assigning the result to the current right child
           }
       }

   // otherwise assume current reference is null
     {
      // create a new node with the data here
     }

   // return the local reference to the calling method
   *
   *
   *

For this situation, the reference to link the current node to the node above is returned at the end whether the method recursed downward or it actually created a new node. Check out this video to see this process in action.

Small Side Step: Traversing A Binary Search Tree

This part isn't about adding new data to a tree but it does apply a couple of interesting algorithms, one of which is necessary for the next discussion. One of the best examples of how BSTs are simple data structures is represented by three forms of iterating across or visiting all the nodes of a tree. Thanks to recursion, the methods for these actions are usually only four or five lines long. Consider the process called in order traversal.

   public void inOrderTraversal( BST_NodeClass localRoot )
     {
      // check for local root not null

          // call recursion to the left

          // display the current data

          // call recursion to the right

In order traversal displays as "left child, parent, right child" and in fact, displays the tree ordered by its keys. Pre order traversal displays as "parent, left child, right child" where the parent comes first (pre), and then post order traversal display as "left child, right child, parent" where the parent comes last (post). The following video shows an in order traversal action.

Constructing A Tree

There are usually only two kinds of constructors for BSTs. The default constructor is one that starts with an empty tree, and that is pretty simple. The tree root reference is set to null. If there is other member data in the BST class, it obvoiusly has to be set up as well but the tree part is pretty easy.

Now for copying a tree, things get a little more interesting but again this is all about drawing pictures and identifying the links that must be made. The first thing to note is that, having seen in this in the previous text, the copy construction process is a pre-order process. It is not a pre order traversal but it conducts its business by processing the parent first, then the left child and then the right child. And as you will note, this and recursion make the copy construction process pretty easy. The copy constructor itself will call a helper method so that the root reference can be passed in to start, and each subsequent root reference is passed in with each call. The helper method will ultimately pass the root reference back to the original copy constructor.

The copy construction helper operation looks like the following:

   public BST_NodeClass( BST_NodeClass localRoot )
     {
      // set a local reference to null

      // check for copied reference not null

          // create a new node to copy current node

          // call recursion to the left,
          // assigning result to the left child of the new node

          // call recursion to the right,
          // assigning result to the right child of the new node

      // return the new local reference, either null or with node

That is about all there is to copying a tree. Once again, recursion is your best friend. This process would be amazingly difficult if recursion was not available. Check out this video -- again with paper and pencil in hand -- to see this method in action.

Putting Data Up Into A Tree

This is about all there is to inserting nodes into BSTs. There can be other variables depending on the data types or how the data is managed but the fundamentals are all here. The most important thing is that you can draw a picture of how each node is created and linked into the tree, and very importantly, in what order. Once you have the drawing part down, you can write any method necessary for the data adding operations.