#include <iostream>

using std::cout;
using std::endl;


struct Node {
  int value;
  Node* pLeft;
  Node* pRight;
};

struct Tree {
  Node* pRoot;
};

Node*
new_node(int value)
{
  Node* node = new Node;
  node->value = value;
  node->pLeft = node->pRight = NULL;
  return node;
}

void
delete_node(Node* pNode)
{
  if(pNode->pLeft)
    delete pNode->pLeft;
  if(pNode->pRight)
    delete pNode->pRight;
  delete pNode;
}

void
insert_node(Node* n, Node* i)
{
  if(i->value <= n->value) {
    if(n->pLeft) {
      insert_node(n->pLeft, i);
    } else {
      n->pLeft = i;
    }
  } else {
    if(n->pRight) {
      insert_node(n->pRight, i);
    } else {
      n->pRight = i;
    }
  }
}

void
insert(Tree& tree, int value)
{
  Node *n = new_node(value);

  if(!tree.pRoot) {
    tree.pRoot = n;
  } else {
    if(n->value <= tree.pRoot->value) {
      if(tree.pRoot->pLeft) {
        insert_node(tree.pRoot->pLeft, n);
      } else {
        tree.pRoot->pLeft = n;
      }
    } else {
      if(tree.pRoot->pRight) {
        insert_node(tree.pRoot->pRight, n);
      } else {
        tree.pRoot->pRight = n;
      }
    }
  }
}

void
print_nodes_inorder(Node *n)
{
  if(n->pLeft) {
    print_nodes_inorder(n->pLeft);
  }

  cout << n->value << endl;

  if(n->pRight) {
    print_nodes_inorder(n->pRight);
  }
}

void
print_sorted(Tree& tree)
{
  Node *n=tree.pRoot;

  print_nodes_inorder(n);
}

int
main()
{
  Tree tree;
  tree.pRoot = NULL;

  int feld[10] = {8, 12, 5, 24, 2, 6, 98, 67, 1, 6};

  for(int i = 0; i < 10; ++i)
    insert(tree, feld[i]);

  print_sorted(tree);

  if(tree.pRoot)
    delete_node(tree.pRoot);

  return 0;
}