#include <iostream>
//#include <cstdlib>
#include <stdlib.h>

class Node {
private:
  int data;
  Node *left, *right;
public:
  static Node *push(Node *root, int data) {
    Node *p;
    if (!root) {
      p = new Node();
      p->data = data;
      p->left = p->right = 0;
      return p;
    } 
    if (data < root->data) {
      root->left = push(root->left, data);
      return root;
    } else {
      root->right = push(root->right, data);
      return root;
    }
  }
  static Node *pop(Node *root, int &data) {
    Node *p;
    if (root == 0)
      return 0;
    if (root->left) {
      root->left = pop(root->left, data);
      return root;
    }
    p = root->right;
    data = root->data;
    delete root;
    return p;
  }
};

class BinTree {
private:
  Node *root;
  bool flag;
public:
  BinTree() {
    root = 0;
    flag = false;
  }
  void pushNode(int data) {
    root = Node::push(root, data);
    flag = true;
  }
  bool popNode(int &data) {
    root = Node::pop(root, data);
    if (!root) {
      if (flag) {
        flag = false;
        return true;
      } else
        return false;
    } else
      return true;
  }
};

int main() {
  const int n = 10;
  const int max = 1000;
  const int seed = 31415926;
  int data;
  BinTree *obj = new BinTree();
  srand(seed);
  for (int i = 0; i < n; i++) {
    data = rand() % max;
    obj->pushNode(data);
  }
  std::cout << "C++(1)" << std::endl;
  while (obj->popNode(data))
    std::cout << data << std::endl;
  delete obj;
  return 0;
}
/* end */