#ifndef TREE_HPP
#define TREE_HPP

#include <vector>
#include <boost/optional.hpp>

template <typename T, int max_children = 2>
class tree : public std::vector< boost::optional
                               < tree< T, max_children > > >
{
private:
  boost::optional<T> data;
public:

  tree() : std::vector< boost::optional
                      < tree< T, max_children > > >
                      (max_children), data()
  {
  }

  tree(const T & some_data) : std::vector< boost::optional
                              < tree< T, max_children > > >
                              (max_children), data(some_data)
  {   
  }  
  
  boost::optional<T> & operator*()
  {
    return data;
  }
  
  const boost::optional<T> & operator*() const
  {
    return data;
  }
};

#endif

#include <iostream>
#include <tree.hpp>

class bst
{
private:
  tree<int> root;
  void insert(tree<int> & pos, int x)
  {
      if (!(*pos))
	*pos = x;
      else
      {
	int child_num = (**pos > x ? 0 : 1);

	if (!pos[child_num])
	  pos[child_num] = tree<int>(x);
	else 
	  insert(*pos[child_num], x);
      }
  }
  
  void inorder_print(tree<int> & pos)
  {
    if (!!*pos)
    {
      if (!!pos[0]) inorder_print(*pos[0]);
      std::cout << " " << **pos << " ";
      if (!!pos[1]) inorder_print(*pos[1]);
    }
  }
  
public:
  bst() : root()
  {
  }

  void insert(int x)
  {
    insert(root, x);
  }
  
  void print()
  {
    inorder_print(root);
    std::cout << std::endl;
  }
  
};

using namespace std;

int main(int argc, char * argv[])
{
  bst t;
  t.insert(10);
  t.insert(5);
  t.insert(11);
  t.insert(12);
  t.insert(6);
  t.print();
  return 0;
}