#include<iostream>
//#include "BSTree.h"

using namespace std;

 


//---------------------------------------------------------------------------
#ifndef BSTreeUnitH
#define BSTreeUnitH
//---------------------------------------------------------------------------
typedef int Item;

class BinSearchTree
{
public:
   BinSearchTree() : root(0) { }
   ~BinSearchTree() { delete root; }

   bool Insert( Item & itm );

protected:
   struct Node
   {
      Item item;
      Node * left;
      Node * right;

      Node( Item & itm, Node * lft, Node * rgt )
       : item(itm), left(lft), right(rgt) { }

      ~Node() { delete left;  delete right; }
   };

   Node * root;

   bool Insert( Node * & node, Item & itm );
};
//---------------------------------------------------------------------------
class Sorting_BST : public BinSearchTree
{
public:
   Sorting_BST() :  BinSearchTree() {  }

   void BST_Sort( Item a[], int n );

private:
   void BST_Sort( Node * node, Item a[], int n, int & k );
};
//---------------------------------------------------------------------------
#endif