#include <iostream.h>

#include <stdlib.h>

struct tree_node {
    tree_node *left;   
    tree_node *right;  

	tree_node *prev;
    
	unsigned int data;

	tree_node();

	tree_node(unsigned int value);

	void print_preorder(tree_node *p);

	void print_postorder(tree_node *p);

	void print_inorder(tree_node *p);

	void setright(tree_node *p);

	void setleft(tree_node *p);
	
	void setprev(tree_node *p);
};

void tree_node::setprev(tree_node *p)
{
	prev=p;
}

void tree_node::setleft(tree_node *p)
{
	left=p;
}

void tree_node::setright(tree_node *p)
{
	right=p;
}

tree_node::tree_node(unsigned int value)
{
	left=NULL;

	right=NULL;

	prev=NULL;

	data=value;
}

void tree_node::print_preorder(tree_node *p) {
    if (p != NULL) {
        
        cout << p->data << "\t"; // print this node
        print_inorder(p->left);  // print left subtree
		print_inorder(p->right); // print right subtree
    }


}



void tree_node::print_postorder(tree_node *p) {
    if (p != NULL) {
        
        print_inorder(p->left);  // print left subtree
		print_inorder(p->right); // print right subtree
    	cout << p->data << "\t"; // print this node
	}

}


void tree_node::print_inorder(tree_node *p) {
    if (p != NULL) {
        
	if(p->left!=NULL)
		print_inorder(p->left);  // print left subtree
        cout << p->data << "\t"; // print this node
        if(p->right!=NULL)
			print_inorder(p->right); // print right subtree
    }

}

tree_node::tree_node()//the node constructor
{
	right=NULL;

	left=NULL;

	prev=NULL;
}
class Search_tree: public tree_node {//class declaration
public:

	void smaller(unsigned int v,tree_node *r);

	Search_tree();

	tree_node *root;

	void additem(unsigned int item);

private:

	tree_node* p_search(unsigned int item, tree_node* node); 

	void p_additem(unsigned int item, tree_node* node);
	
};

void Search_tree::smaller(unsigned int v, tree_node *r)
{
if (r != NULL&&r->data<v) {

        smaller(v,r->left);  // print left subtree
		smaller(v,r->right); // print right subtree
		cout << r->data << endl; // print this node
	}
}

void Search_tree::additem(unsigned int item) //Adds an item to the tree, automatically sorting it.

{

      if(root == NULL)           //If the list is empty...
	  {
        root = new tree_node(item); //Make the new node the parent.

		cout<<"The root node is added\n";
	  }

      else if (p_search(item,root)==NULL)

        p_additem(item, root); //Call the private, recursive, function for adding nodes

	  else if (p_search(item,root)!=NULL)
		  cout<<"Value already exists!\n";
}

 
tree_node* Search_tree::p_search(unsigned int item, tree_node* node) //Private, recursive, function for searching.

     {

      if(node != NULL) //If the node is not NULL...

       {

        if(item == node->data) //If we have found the node...

          return node;           //Return it.

        if(item < node->data)  //If the node's data is greater than the search item...

          return p_search(item, node->left);  //Search the left node.

        else                     //If the node's data is less than the search item...

          return p_search(item, node->right); //Search the right node.

       }

      else

        return NULL; //If the node is NULL, return NULL.

     }

 

void Search_tree::p_additem(unsigned int item, tree_node* node)

{
	
	{

      if(item < node->data) //If the adding item is less than the current node's data...

       {

        if(node->left != NULL)         //If there is a left node...
		{
          p_additem(item, node->left); //Add the new node to it.

		
		}

        else                             //If there is not a left node...

         {

          tree_node* current = new tree_node(item); //Make the new node.

          node->setleft(current);             //Make it the left node of the current one.

          current->setprev(node);             //Set the new node's previous node.

				cout<<"The item was added to the left side of the tree\n";

         }  

       }

      else if(item > node->data) //If the adding item is greater than the current node's data...

       {

        if(node->right != NULL)         //If there is a right node...

          p_additem(item, node->right); //Add the new node to it.

        else                              //If there is not a right node...

         {

          tree_node* current = new tree_node(item); //Make the new node.

          node->setright(current);            //Make it the left node of the current one.

          current->setprev(node);             //Set the new node's previous node.

				cout<<"The item was added to the right side of the tree\n";

         }

       }
	}
}


Search_tree::Search_tree()
{
	root=NULL;
}


void main()

{

	Search_tree tree;

	unsigned int value;


		cout<<"Enter five values to the tree: "<<endl;
		for(int i=0;i<5;i++)
		{
			cin>>value;
			tree.additem(value);

		}
		cout<<"Printing tese values in preorder: ";
	
		tree.print_preorder(tree.root);
				cout<<endl;

	
		cout<<"Printing tese values in inorder: ";
	
		tree.print_inorder(tree.root);
				cout<<endl;

		
		cout<<"Printing tese values in preorder: ";
	
		tree.print_postorder(tree.root);
				cout<<endl;

	
		cout<<"Enter a value to check all values less than it: ";
		cin>>value;
			tree.smaller(value,tree.root);
				cout<<endl;


}