// yasuhara, 15 Aug 2000


struct BinTreeNode {
  // item stored at this node
  int data;
  // ptrs. to children (left, right subtrees)
  BinTreeNode *left, *right;
};


// implements Magic Trick in Slide X-21
// assumes BSTInsert is defined as in Slide X-12 
// assumes treeDeallocate deletes all BinTreeNodes in given tree
// http://www.cs.washington.edu/education/courses/143/00su/slides/X-binarysearchtrees.pdf
void
BSTSort(int A[], const int n) 
{
  BinTreeNode *tmpTree = NULL;

  for (int i = 0; i < n; i++) {
    BSTInsert(tmpTree, A[i]);
  }
  
  int retrievedCount = retrieveInOrder(A, tmpTree);
  assert(retrievedCount == n);

  treeDeallocate(tmpTree);
  tmpTree = NULL;
}


// traverses tree in-order, storing items into array; A must be big
// enough to store all items in tree; returns number of items stored
// in A
int
retrieveInOrder(int A[], BinTreeNode *r)
{
  int addedCount = 0;
  retrieveInOrderHelper(A, addedCount, r);
  return addedCount;
}


int
retrieveInOrderHelper(int A[], int &addedCount, BinTreeNode *r)
{
  assert(addedCount >= 0);
    
  // base case
  if (r == NULL)		
    return;

  // recursive case
  retrieveInOrderHelper(A, addedCount, r->left);
  A[addedCount] = r->data;
  addedCount++;
  retrieveInOrderHelper(A, addedCount, r->right);
}