Program For Binary Tree Traversal Without Recursion

      /* Program For Binary Tree Traversal Without Recursion */
#include<iostream.h>
#include<conio.h>
#include<process.h>
#include<alloc.h>


class BinaryTree
{
    private:
	struct tree_node
	{
	   tree_node* left;
	   tree_node* right;
	   int data;
	};
	tree_node * root;

    public:
	BinaryTree()
	{
	   root = NULL;
	}
	int isEmpty()
	{
		if(root==NULL)
			return 1;
		else
			return 0;
	}
	void inorder();
	void preorder();
	void postorder();
	void insert(int);
};

void BinaryTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;
  // is this a new tree?
  if(isEmpty()) root = t;
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* curr;
    curr = root;
    // Find the Node's parent
    while(curr)
    {
	parent = curr;
	if(t->data > curr->data)
		curr = curr->right;
	else
		curr = curr->left;
    }

    if(t->data < parent->data)
       parent->left = t;
    else
       parent->right = t;
  }
}

void BinaryTree::inorder()
{
		tree_node *stack[20],*ptr=root;
		int top=-1;

		while(top!=-1 || ptr!=NULL)
		{
			if(ptr!=NULL)
			{
				stack[++top]=ptr;
				ptr=ptr->left;
			}
			else
			{
				ptr=stack[top--];
				cout<<ptr->data<<" ";
				ptr=ptr->right;
			}
		}
}

void BinaryTree :: preorder()
{
		tree_node *stack[20],*ptr;
		int top=-1;

		stack[++top]=root;

		while(top!=-1)
		{
			ptr=stack[top--];

			if(ptr!=NULL)
			{
				cout<<ptr->data<<" ";
				stack[++top]=ptr->right;
				stack[++top]=ptr->left;
			}
		}
}

void BinaryTree :: postorder()
{
	tree_node *stack[20],*ptr;
	int top=-1,v;

	ptr=root;
	v=0;

	if(ptr!=NULL)
	{
		stack[++top]=ptr;
		stack[++top]=(tree_node*)1;
		ptr=ptr->left;

		while(top!=-1)
		{
			if(ptr!=NULL && v==0)
			{
				stack[++top]=ptr;
				stack[++top]=(tree_node*)1;
				ptr=ptr->left;
			}
			else
			{
				v=(int)stack[top--];
				ptr=stack[top--];
				if(v==1)
				{
					stack[++top]=ptr;
					stack[++top]=(tree_node*)2;
					ptr=ptr->right;
					v=0;
				}
				else
					cout<<ptr->data<<" ";
			}
		}
	}
}

void main()
{
	BinaryTree bt;
	int ch,d;
	clrscr();

	while(1)
	{
		cout<<"\n1.create\n2.inorder\n3.preorder\n4.postorder\n5.exit";
		cout<<"\nEnter your choice: ";
		cin>>ch;

		switch(ch)
		{
			case 1:  char c='y';
				while(c=='y')
				{
					cout<<"\nEnter data to insert: ";
					cin>>d;
					bt.insert(d);
					cout<<"\nDo you want to continue (y/n): ";
					cin>>c;
				}
				break;

			case 2:
				if(bt.isEmpty())
					cout<<"\nTree empty";
				else
				{
					cout<<"Inorder Traversal is: ";
					bt.inorder();
				}
				break;

			case 3:
				if(bt.isEmpty())
					cout<<"\nTree empty";
				else
				{
					cout<<"Preorder Traversal is: ";
					bt.preorder();
				}
				break;

			case 4:
				if(bt.isEmpty())
					cout<<"\nTree empty";
				else
				{
					cout<<"Postorder Traversal is: ";
					bt.postorder();
				}
				break;

			case 5:
				exit(0);
		}
	}
}