// This Program creates a binary search tree of integers and introduces      //
// the inorder recursive traversal of the tree. It is the basis for Project 5//
//  D. Pinto....CS 501...LATE Spring 2011                                 //



#include <iostream>
using namespace std;

const int nil = 0;
class treenode_type		    // declaration of class//
{
public:						// Tree node type//
		int info;
		treenode_type *left;
		treenode_type *right;
};

void setleft(int x);
void setright(int x);
void inorder(treenode_type *p);
treenode_type *p,*q,*root;
int number, counter=0;
void main()
{
    cout << "Enter first value: \n";
	cin >> number;
	cout << number << "\n";
	root = new treenode_type;
	(*root).info = number;
	(*root).left = nil;
	(*root).right = nil;
	cout <<"Enter 19 more numbers\n";
	cin >> number;
	while (counter < 18)
	{
		p = root;
		q = p;
		while ((number != (*p).info) && (q!=nil))
		{
			p = q;
			if (number < (*p).info)
				q = (*p).left;
			else
				q = (*p).right;
		}
		if (number == (*p).info)
			cout << number << " is a duplicate \n";
		else if (number < (*p).info)     // Sets node to left if number less than p.info//
		{
			setleft(number);
			cout << number <<" is a left child of "<< (*p).info << "\n";
		}
		else    // Sets node to right if number greater than p.info//
		{
			setright(number);
			cout << number <<" is a right child of "<< (*p).info << "\n";
		}
		cin >> number;
		counter++;
	}
	cout << "The tree traversed INORDER is \n";
	p = root;
	inorder(p);
}

void setleft(int x)   // Sets node to left //
{
	treenode_type *q;
	q = new treenode_type;
	(*q).info = x;
	(*q).left = nil;
	(*q).right = nil;
	(*p).left = q;
}
void setright(int x)
{
	treenode_type *q;
	q = new treenode_type;
	(*q).info = x;
	(*q).left = nil;
	(*q).right = nil;
	(*p).right = q;
}
void inorder(treenode_type *r)
{
  if (r != nil)
	{
	inorder((*r).left);
	cout << (*r).info << "\n";
	inorder((*r).right);
	}
}