Treesort algorithm

[smoothe19]

A binary search tree can be used to sort a list. WE simply insert the list elements into a BST, initially empty, and then use an inorder traversal to copy them back into the list. Write an algorithm for this treesort method of sorting, assuming that the list is stored in

a. an array
b. a linked list

any tips, suggestions, help is very much appreciated

Merci beau coup!

[daviddoria]

French or not, you're going to have to show us that you have tried. We are not going to do your assignment for you, but we'd be happy to teach you something along the way!

[smoothe19]

French or not, you're going to have to show us that you have tried. We are not going to do your assignment for you, but we'd be happy to teach you something along the way!

Sorry forgot to add my code

Here is my insert function and inorder traversal are these correct?
As in is it an efficient way to sort LinkedLists when passed through the insert and then the inorder?

//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
   BST<DataType>::BinNodePointer 
        locptr = myRoot,   // search pointer
        parent = 0;        // pointer to parent of current node
   bool found = false;     // indicates if item already in BST
   while (!found && locptr != 0)
   {
      parent = locptr;
      if (item < locptr->data)       // descend left
         locptr = locptr->left;
      else if (locptr->data < item)  // descend right
         locptr = locptr->right;
      else                           // item found
         found = true;
   }
   if (!found)
   {                                 // construct node containing item
      locptr = new(nothrow) BST<DataType>::BinNode(item);  
      if (locptr == 0)	
      {
        cerr << "*** Out of memory -- terminating program ***\n";
	exit(1);
      }

      if (parent == 0)               // empty tree
         myRoot = locptr;
      else if (item < parent->data )  // insert to left of parent
         parent->left = locptr;
      else                           // insert to right of parent
         parent->right = locptr;
   }
   else
      cout << "Item already in the tree\n";
}

Here is my inorder traversal...

/--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(ostream & out) const
{ 
   inorderAux(out, myRoot); 
}

//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(ostream & out, 
                               BinNodePointer subtreeRoot) const
{
   if (subtreeRoot != 0)
   {
      inorderAux(out, subtreeRoot->left);    // L operation
      out << subtreeRoot->data << "  ";      // V operation
      inorderAux(out, subtreeRoot->right);   // R operation
   }
}