C++ Binary Search Tree Insert via Recursion

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);
      }
   }

From stackoverflow Doug

• 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));
  }
  

  Doug : so you think my insert is correct? I mean based on my debug prints... and physically writing this down... everything seems to match.

  Doug : Yeah your height gave me the same value as mine. It looks cleaner and is more effecient though so I appreciate it.

  SyaZ : A little correction, if(root = NULL) should be root == NULL.
  From Martin York

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

  Martin York : No he needs the reference to make the assignment work correctly. Though it is ugly I will give you that.
  From Paul Nathan

• @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)

  Doug : Thanks for the help. So I'll try changeing it around like you said, but technically our code is doing the same things though right?

  Doug : I also forgot to add that while I didn't go as far as you did in making a function to drawing out the tree, Based on the debug prints, and my own drawing of the pre defined hard coded numbers that are inserted.. It appears to be doing it correctly. I sent it off to my TA in hopes he can clarify.

  aib : Yes, they both are doing the same thing; the difference is cosmetic. The code looks correct, the problem is (as Martin York has pointed out) printing "root found" while the node is actually just the root of the new subtree. (i.e. a leaf)
  From aib