C++ Binary Search Tree Insert via Recursion

Question

So my code is below. I'm not getting any errors and it places everything in the node just fine. But based on my debug statements Everytime anything is inserted it's finding the root. I'm not sure if that is right. But according to output file for the assignment, my answers are different when it comes to the height of the tree, the traversals, and I just flat am still having troubles with my leaf count function. Another story though.

Based on the debug statements it looks like everything is going right where they should. But I figure I might need fresh eyes. I don't see how my traversals could change at all since it is really only a matter of where I'm proccessing the node that should effect the Inorder, preorder, and postorder.

template <class T>
void BT<T>::insert(const T& item)
 {
    Node<T>* newNode;
    newNode = new Node<T>(item);
    insert(root, newNode);
 }


template <class T>
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode)
 {
    if (root == NULL)
       {
          cout << "Root Found" << newNode->data << endl;
          root = newNode;
       }
    else
        {
           if (newNode->data < root->data)
              {
              insert(root->left, newNode);
              cout << "Inserting Left" << newNode-> data << endl;
              }
           else
               {
               insert(root->right, newNode);
               cout << "Inserting Right" << newNode->data << endl;
               }
        }
 }

My height function is as follows just in case my insert is actually fine.

template <class T>
int BT<T>::height() const
{
   return height(root);
}


  template <class T>
  int BT<T>::height(Node<T>* root) const
   {
   if (root == NULL)
      return 0;
   else 
      {
      if (height(root->right) > height(root->left))
         return 1 + height(root-> right);
      return 1 + height(root->left);
      }
   }

Answer 1

You need to change the wording of your debug statements

Really it should read (not Root node)

 cout << "Leaf Node Found" << newNode->data << endl;

It is only the root when it is first called after that any call with node->left or node->right makes it an intermediate node.

To write height() I would do this:

template <class T>
int BT<T>::height(Node<T>* root) const
{
    if (root == NULL) {return 0;}

    return 1 + max(height(root->left),height(root->right));
}

Answer 2

You need to start off with your root init'd to null. Also, you are passing *&node in; it should be *node. Else you're passing a pointer to the address(or reference, I'm not sure which in this context, but both aren't going to be right). You should be passing a pointer to Node in, not a reference.

template <class T>
void BT<T>::BT() 
{ root = 0;}

template <class T>
void BT<T>::insert(const T& item)
 {
    Node<T>* newNode;
    newNode = new Node<T>(item);
    insert(root, newNode);
 }

template <class T>
void BT<T>::insert(struct Node<T> *root, struct Node<T> *newNode)
{
 /*stuff*/
}

Answer 3

@Vlion:
It should be a pointer to the left/right/root pointers (i.e. a double pointer), so the posted code is correct, although somewhat unclear.

@Doug:
Consider changing your insert function thus:

template <class T>
void BT<T>::insert(struct Node<T>** root, struct Node<T>* newNode)
 {
    if (*root == NULL)
       {
          cout << "Root Found" << newNode->data << endl;
          *root = newNode;
       }

It makes clear your intention that you'll be changing the pointer passed as the first parameter (or rather, the pointer whose address will be passed as the first parameter.) It will help avoid confusion such as the one that just happened.

The calls to this insert(), such as:

insert(&root, newNode);

will also reflect your intention of changing the pointer's value. This is a matter of style, though, so I can't argue if you don't want to change.

---

As for checking whether the tree is "correct," why not draw it out and see for yourself? Something along the lines of:

template class<T>
void printTree(struct Node<T>* node, int level=0)
{
    if (!node) {
        for (int i=0; i<level; ++i)
            cout << "  ";
        cout << "NULL" << endl;

        return;
    }

    printTree(node->left, level+1);

    for (int i=0; i<level; ++i)
        cout << "  ";
    cout << node->data << endl;

    printTree(node->right, level+1);
}

(Untested code)