C++ print out a binary search tree

Question

Got nothing better to do this Christmas holiday, so I decided to try out making a binary search tree. I'm stuck with the print function. How should the logic behind it work? Since the tree is already inserting it in a somewhat sorted order, and I want to print the tree from smallest values to the biggest.

So I need to travel to the furthest left branch of the tree to print the first value. Right, so after that how do I remember the way back up, do I need to save the previous node? A search in wikipedia gave me an solution which they used stack. And other solutions I couldn't quite understand how they've made it, so I'm asking here instead hoping someone can enlight me.

I also wonder my insert function is OK. I've seen other's solution being smaller.

void treenode::insert(int i)
{

   if(root == 0)
   {
      cout << "root" << endl;
      root = new node(i,root);
   }
   else
   {
      node* travel = root;
      node* prev;
      while(travel)
      {
         if(travel->value > i)
         {
            cout << "travel left" << endl;
            prev = travel;
            travel = travel->left;
         }
         else
         {
            cout << "travel right" << endl;
            prev = travel;
            travel = travel->right;
         }
      }
      //insert
      if(prev->value > i)
      {
         cout << "left" << endl;
         prev->left = new node(i);
      }
      else
      {
         cout << "right" << endl;
         prev->right = new node(i);
      }
   }

}

void treenode::print()
{

   node* travel = root;
   while(travel)
   {
      cout << travel->value << endl;
      travel = travel->left;
   }

}

Solution

You can use recursion (pseudocode):

prin-tree(node):
   print-tree(left-subnode) if exists
   print(node-value)
   print-tree(right-subnode) if exists
...
print(root-of-tree)

Comments

[starcorn]

funny thing it works. Not so funny is that I don't understand it... I hate recursion...

[T.E.D.]

@starcorn - If you feel that way about recursion, my suggestion would be drop this project and take up writing programs in Lisp for a while until you are comfortable with it. There are reasons to avoid it on occasion, but to be a truly expert developer recursion needs to be in your toolbox.

[abRao]

@starcorn - for the uninitiated recursion can be daunting - most of us go through that! Here is an easy way to understand recursion - the "crux" of a recursive call is not in the recursion itself, rather it is in the "end cases", viz., the parts of the code that execute when you are not going to do a recursive call. Start by trying to understand the print functions - the difference version postorder, preorder and inorder. A quick search showed up this web page cs.umd.edu/class/spring2002/cmsc214/Tutorial/recursion.html