Untitled

//============================================================================
// Name        : Assignment3.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

// 21143 Tanmay Karmarkar
// DSAL Assignment 3
// Create an inordered threaded binary tree and perform inorder and preorder traversals.
// Analyze space and time complecity of the algorithm.

#include<iostream>
using namespace std;

// Structure of the node .
struct Node
{
 int data;
 Node*left;
 Node*right;
 bool lbit;
 bool rbit;
};

//Function to create a node and return the address of the node created.
Node* newnode(int data)
{
Node*temp=new Node;
temp->data=data;
temp->left=NULL;
temp->right=NULL;
temp->lbit=1;
temp->rbit=1;
return temp;
};

Node*Pred(Node*root)
{
Node*temp=root;

if(temp==NULL)
	return NULL;
while(temp->right!=NULL)
temp=temp->right;

return temp;
};
Node *Succ(Node*root)
{
	Node*temp=root;
	if(temp==NULL)
		return NULL;
	while(temp->left!=NULL)
		temp=temp->left;
	return temp;
}

//Function to create the TBT
Node*create(Node*root)
{
int x;
cout<<"Enter data"<<endl;
cin>>x;
Node*temp=newnode(x);
if (x==-1)
{
return NULL;
}
if (root==NULL)
{
  root=temp;
}
cout<<"Enter left of "<<x<<": ";
temp->left=create(temp->left);
cout<<"Enter right of "<<x<<": ";
temp->right=create(temp->right);

Node * p=Pred(temp->left);
Node * s=Succ(temp->right);

if(p!=NULL)
{
	if(p->right==NULL)
	{
		p->right=temp;
		p->rbit=0;
	}
}
if(s!=NULL)
{
	if(s->left==NULL)
	{
		p->left=temp;
		p->lbit=0;
	}
}
return root;
};


//Function to create the head pointer for the tree
//Node* create_head(Node*head)
//{
  //Node*temp=newnode(-1);
  //head=temp;
  //return head;
//}
int main()
{
Node*root=NULL;
//head=create_head(head);

root=create(root);
return 0;
}