#include <iostream>
#include <queue>

using namespace std;

template<class T>
struct Node{
public:
	Node(){
		left = right = 0;
	}
	
	Node(const T& data_in){
		value = data_in;
		left = right = 0;
	}
		
	T value;
	Node *left, *right;
};

template<class T>
class BinaryTree{
public:
	BinaryTree(){
		root = 0;
	}
	
	bool insert(const T& in_value){
		
		if(root == 0){
			root = new Node<T>(in_value);
		}else{
			Node<T> *temp = root, *temp_old;
			while(temp != 0){
				temp_old = temp;
				
				if(temp->value = in_value){
					return false;
				}else if (temp->value < in_value){
					temp = temp->right;
				}else if (temp->value > in_value){
					temp = temp->left;
				}
			}
			
			Node<T> *new_node;
			new_node = new Node<T>(in_value);
			
			if (temp_old->value > in_value){
				temp_old->left = new_node;
			}else{
				temp_old->right = new_node;				
			}
		}
		
		return true;
	}
	
	void preorder_print(){		
		queue< Node<T> > new_queue;
		Node<T> *temp;
		
		new_queue.push(*root);
		while(!new_queue.empty()){
			*temp = new_queue.front();
			new_queue.pop();
			
			cout << temp->value;
			new_queue.push(*temp->left);
			new_queue.push(*temp->right);
		}
	}

	Node<T> *root;
};

int main(){
	BinaryTree<int> int_tree;
	
	int a=1,b=2,c=3;
	
	int_tree.insert(b);
	int_tree.insert(a);
	int_tree.insert(c);
	
	int_tree.preorder_print();
	
	return 0;
};