//	binary tree
//
//	p.479

#include <iostream>
using namespace std;

// p.480
struct TreeNode
{	int info;
	TreeNode* left;
	TreeNode* right;
};

class TreeType
{
	TreeNode* root;
public:
	// p.501
	TreeType()
	{
		root = NULL;
	}
	~TreeType()
	{
		Destroy(root);
	}
	void Destroy (TreeNode*& tree)
	{
		if( tree != NULL )
		{
			Destroy(tree->left);
			Destroy(tree->right);
			delete tree;
		}
	}
	// p.491
	void InsertItem(int item)
	{
		Insert(root, item);
	}
	void Insert(TreeNode*& tree, int item)
	{
		if(tree==NULL)
		{
			tree = new TreeNode;
			tree->right = tree->left = NULL;
			tree->info = item;
		}
		else if ( item < tree->info )
			Insert(tree->left, item);
		else
			Insert(tree->right, item);
	}
	// p.500
	void Print() const
	{
		PrintTree(root);
	}
	void PrintTree(TreeNode* tree) const
	{
		if(tree!= NULL)
		{
			PrintTree(tree->left);
			cout << tree->info << " ";
			PrintTree(tree->right);
		}
	}			

};

int main()
{

	TreeType me;
	me.InsertItem(27);
	me.InsertItem(14);
	me.InsertItem(67);
	me.InsertItem(4);
	me.InsertItem(17);
	
	me.Print();

	cout << "\n\nDone.\n\n";
	return 0;
}