Create an inordered threaded binary tree and perform inorder and preorder traversals. Analyze time and space complexity of the algorithm

	/*
	* Threaded.cpp
	*
	* Created on: Feb 5, 2019
	* Author: iamrohitsuthar
	*/
	#include<iostream>
	using namespace std;
	const int MAX=30;
	class Node {
	int lbit;
	int rbit;
	Node* left;
	Node* right;
	char data;
	public:
	Node() {
	lbit=0;
	rbit=0;
	left=NULL;
	right=NULL;
	data=0;
	}
	Node(int lbit,int rbit, char data) {
	this->lbit=lbit;
	this->rbit=rbit;
	this->data=data;
	left=NULL;
	right=NULL;
	}
	friend class ThreadedTree;
	};
	class Queue {
	Node* items[MAX];
	int rear;
	int front;
	public:
	Queue() {
	rear=front=-1;
	}
	void insertQ(Node* node) {
	if(!isFull()) {
	if(isEmpty())
	rear=front=0;
	else
	rear=rear+1;
	items[rear]=node;
	}
	}
	Node* deleteQ() {
	Node* temp;
	if(!isEmpty()) {
	temp=items[front];
	if(front==rear) {
	front=rear=-1;
	}
	else
	front=front+1;
	return temp;
	}
	}
	int isEmpty() {
	if(rear==-1)
	return 1;
	return 0;
	}
	int isFull() {
	if(rear==MAX-1)
	return 1;
	return 0;
	}
	};
	class ThreadedTree {
	Node* head;
	public:
	ThreadedTree() {
	head=NULL;
	}
	Node* getHead() {
	return head;
	}
	void create() {
	Queue q;
	char ch;
	char choice;
	Node* temp;
	Node* x;
	head= new Node(0,1,'P');
	head->left=head->right=head;
	q.insertQ(head);
	while(!q.isEmpty()) {
	temp=q.deleteQ();
	cout<<"Do you want to set left data for "<<temp->data<<" (Y/N): ";
	cin>>choice;
	if(choice=='Y' || choice=='y') {
	cout<<"Enter left data for "<<temp->data<<": ";
	cin>>ch;
	if(ch != 0) {
	x=new Node();
	x->data=ch;
	Linsert(temp,x);
	q.insertQ(x);
	}
	}
	if(temp != head) {
	cout<<"Do you want to set right data for "<<temp->data<<" (Y/N): ";
	cin>>choice;
	if(choice=='Y' || choice=='y') {
	cout<<"Enter right data for "<<temp->data<<": ";
	cin>>ch;
	if(ch != 0) {
	x=new Node();
	x->data=ch;
	Rinsert(temp,x);
	q.insertQ(x);
	}
	}
	}
	}
	}
	void Rinsert(Node* first,Node* second) {
	//second as a right child of first
	second->right=first->right;
	second->rbit=first->rbit;
	second->left=first;
	second->lbit=0;
	first->right=second;
	first->rbit=1;
	}
	void Linsert(Node* first,Node* second) {
	second->left=first->left;
	second->lbit=first->lbit;
	second->right=first;
	second->rbit=0;
	first->left=second;
	first->lbit=1;
	}
	void inorder(Node* temp) {
	Node* root=temp;
	cout<<"Inorder is: ";
	while(1) {
	temp=insucc(temp);
	if(temp==root)
	return;
	if(temp->data != root->data)
	cout<<temp->data<<" ";
	}
	}
	Node* insucc(Node* temp) {
	Node* s;
	s=temp->right;
	if(temp->rbit==1) {
	while(s->lbit==1) {
	s=s->left;
	}
	}
	return s;
	}
	void preorder(Node* root) {
	int flag=1;
	Node* temp=root->left;
	cout<<"Preorder is: ";
	while(temp != root) {
	while(flag==1) {
	cout<<temp->data<<" ";
	if(temp->lbit==1)
	temp=temp->left;
	else
	break;
	}
	flag=temp->rbit;
	temp=temp->right;
	}
	}
	};
	int main() {
	ThreadedTree t;
	int choice;
	char ch;
	do {
	cout<<"1. For Create tree \n";
	cout<<"2. For Inorder traversal \n";
	cout<<"3. For preorder traversal \n";
	cout<<"Enter your choice: ";
	cin>>choice;
	switch(choice) {
	case 1: t.create();
	break;
	case 2: t.inorder(t.getHead());
	cout<<endl;
	break;
	case 3: t.preorder(t.getHead());
	cout<<endl;
	break;
	}
	cout<<"Do you want to continue (Y/N): ";
	cin>>ch;
	}while(ch=='y' || ch=='Y');
	return 0;
	}

view raw ThreadedBinaryTree.cpp hosted with ❤ by GitHub