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.

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 pointer below is not NULL, then the operation must recursively track that pointer down to the next node which will again look down, and so on. Again, recursion makes this operation pretty straightforward, as shown here. However, this strategy would require initialization of the head pointer prior to calling this add node operation since it must start from a node.

// inside add/insert function

   // 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 function 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 function above will check for the NULL before it moves downward. Consider the following code.

// inside add/insert function

   // check for bottom of tree (NULL)
      {
       //create a new node with the data here
       // and return its pointer to the parent/calling function
      }

    // 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
       }
   }
   *
   *
   *

For this situation, the reference to link the current node to the node above is returned at the end whether the function 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 functions for these actions are usually only four or five lines long. Consider the process called in order traversal. A C version is shown but the differences between C and C++ are negligible here.

void displayTreeInOrder( BST_Node *currentNodePtr )
   {
    // check for current node not null
    if( currentNodePtr != NULL )
       {
        // recurse to the left
           // function: displayTreeInOrder (recursive)
        displayTreeInOrder( currentNodePtr->leftChildPtr );

        // display current node value
           // function: printf
        printf( "Name: %s, Student ID: %d, Gender: %c, GPA: %4.2f\n",
                 currentNodePtr->name, currentNodePtr->studentId, 
                              currentNodePtr->gender, currentNodePtr->gpa );

        // recurse to the right
           // function: displayTreeInOrder (recursive)
        displayTreeInOrder( currentNodePtr->rightChildPtr );
       }
   }

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 pointer is set to NULL. If there is other member data in the BST class, it obviously 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 function so that the root pointer can be passed in to start, and each subsequent root pointer is passed in with each call. The helper function will ultimately pass the root pointer back to the original copy constructor. Again, there is very little difference between C and C++ for this function.

The copy construction helper operation -- called copyTree -- looks like the following:

BST_Node *BST_Class::copyTree
       ( 
        const BST_Node *copiedCurrentPtr   // in: pointer to current location
                                           // in copied tree
       )
   {
    // initialize function/variables

    // check for copied node 
       {
        // create new node
           // function: new

        // set left child to left recursion
           // function: copyTree (recursive)

        // set right child to right recursion
           // function: copyTree (recursive)
       }

    // return pointer to new node
   }

This video will walk you through the copying process. Make sure you can replicate all of the actions here. This will help you understand not just the copy process, but a significant part of the general linking process.

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 function necessary for the data adding operations.