treesort.cpp

#include <iostream>

using namespace std;

class Node {
private:
  bool hasValue_;
  int value_;
  Node *left_;
  Node *right_;

public:
  Node(int value);
  // sorts the array in place.
  static void Sort(int *arr, int size);
  void Add(int value);
  bool IsEmptyNode();
  int Pop();
};

Node::Node(int value){
  hasValue_ = true;
  value_ = value;
  left_ = NULL;
  right_ = NULL;
}
void Node::Add(int value){
  // regular version
  // if (value <= value_){
  //   // Value less or equal, go left.
  //   if (!left_)
  //     left_ = new Node(value);
  //   else
  //     left_->Add(value);
  // }
  // else {
  //   // Value greater.
  //   if (!right_)
  //     right_ = new Node(value);
  //   else
  //     right_->Add(value);
  // }

  // Sexy version
  Node **ptr = value <= value_? &left_ : &right_;
  if (*ptr)
    (*ptr)->Add(value);
  else
    *ptr = new Node(value);
}

bool Node::IsEmptyNode(){
  return !(left_ || right_ || hasValue_);
}

// Pop and return the first value from the tree (recursively).
int Node::Pop() {
  int ret_val = 0;

  // Look to return the left node, then this node, then the right node, in that order.
  if (left_){
    ret_val = left_->Pop();
    if (left_->IsEmptyNode()){
      delete left_;
      left_ = NULL;
    }
  }
  else if (hasValue_){
    hasValue_ = false;
    ret_val = value_;
  }
  else if (right_){
    ret_val = right_->Pop();
    if (right_->IsEmptyNode()){
      delete right_;
      right_ = NULL;
    }
  }

  return ret_val;
}

void Node::Sort(int *arr, int size){
  Node *root = new Node(arr[0]);
  for (int i = 1; i < size; i++){
    root->Add(arr[i]);
  }

  int i = 0;
  while (!root->IsEmptyNode())
    arr[i++] = root->Pop();

  delete root;
}



// --- TESTING ---

void PrintLst(int *arr, int size){
  cout << "______________" << endl;
  for (int i = 0; i < size; i++) cout << arr [i] << endl;
}

int main() {
  const int size = 100;
  int lst[size] = {494, 39 , 543, 178, 650, 898, 811, 193, 208, 714, 565, 804, 215, 628, 676, 299,
                   275, 352, 131, 161, 376, 697, 783, 410, 744, 906, 462, 617, 701, 842, 471, 800,
                   764, 463, 74 , 116, 231, 586, 196, 504, 923, 774, 897, 315, 532, 576, 539, 675,
                   728, 476, 575, 999, 704, 145, 870, 107, 493, 154, 906, 925, 711, 194, 161, 457,
                   231, 824, 208, 466, 881, 105, 791, 670, 728, 534, 29 , 715, 555, 716, 455, 808,
                   298, 197, 372, 903, 867, 554, 554, 457, 910, 515, 608, 437, 531, 629, 428, 875,
                   761, 762, 29 , 891};

  PrintLst(lst, size);
  Node::Sort(lst, size);
  PrintLst(lst, size);
}