/* tbt */

#include <stdio.h>
#include <alloc.h>

enum boolean {
false = 0,
true = 1
};

typedef struct node {
enum boolean isleft;
struct thtree *left;
int data;
struct thtree *right;
enum boolen isright;
}thtree;


void insert (thtree **, int);
void del (thtree **, int);
void search (thtree **, int, thtree **, thtree **, int *);
void inorder (thtree *);
void deltree (thtree **);


void main()
{
int ch;
char *ch_temp;
if (!(ch = malloc(TEMP))) {
printf("\nError in memory allocation\n");
exit(FAILURE);
}
while(1) {
get(ch_temp);
if (isno(ch_temp) == SUCCESS) {
printf("\nInvalid input\n");
continue;
}
if (choice(ch) == SUCCESS)
break;
}
FREE(ch_temp);
return SUCCESS;
}


/* Get choice from user */

int choice(int ch)
{
char *temp;
thtree *th_head;
th_head = NULL;

if (!(temp = malloc( TEMP)) {
printf("\nError in memory allocation\n");
exit(FAILURE);
}

switch(ch) {
case 1:
printf("\nEnter the element to insert\n");
while (1) {
get(temp);
if ((isno(temp) == SUCCESS) || ((item = stono(temp)) == MAX))
printf("\nInvalid input\n");
else
break;
}

insert (&th_head, item);
break;
case 2 :
printf("\nEnter the element to delete\n");
while (1) {
get(temp);
if ((isno(temp) == SUCCESS) || ((item = stono(temp)) == MAX))
printf("\nInvalid input\n");
else
break;
}

del (&th_head, item);
break;
case 3 :
display(th_head);
break;
case 4 :
FREE (th_head);
return SUCCESS;
default :
printf("\nInvalid input\n\n");
}
return FAILURE;
}


/* insert a node in threaded binary tree */

void insert (thtree **s, int num)
{
thtree *p, *z, *head = *s ;

if (!(z = malloc(TBT))) {
printf("\nError in allocating memory for node");
return;
}

z -> isleft = true;
z -> data = num;
z -> isright = true;

if (*s == NULL) {
if (!(head = malloc(TBT))) {
printf("\nError in allocating memory for node");
return;
}

        /* the entire tree is treated as a left sub-tree of the head node */

head -> isleft = false;
head -> left = z;
head -> data = -9999;
head -> right = head;
head -> isright = false;
*s = head;
z -> left = head;
z -> right = head;
} else {
p = head -> left;
        /* traverse till the thread is found attached to the head */

while (p != head) {
if (p -> data > num) {
if (p -> isleft != true)
p = p -> left;
else {
z -> left = p -> left;
p -> left = z;
p -> isleft = false;
z -> isright = true;
z -> right = p;
}
}
else if (p -> data < num) {
if (p -> isright != true)
p = p -> right;
else {
z -> right = p -> right;
p -> right = z;
p -> isright = false;
z -> isleft = true;
z -> left = p;
}
}
else if (p -> data == num) {
printf("\nData duplication. Insertion failed.\n");
return;
}
}
}
printf("\nNode inserted\n\n");
}


/* delete a node from threaded binary tree */
void del(thtree **root, int num)
{
int found;
thtree *parent, *x, *xsucc;

    /* if tree is empty */
if (*root == NULL) {
printf("\nTree is empty");
return;
}

parent = x = NULL;

search(root, num, &parent, &x, &found);

if (found == false) {
printf("\nData not found\n");
return;
}

/* if the node to be deleted has two children */

if ((x -> isleft == false) && (x -> isright == false)) {
parent = x;
xsucc = x -> right;
while (xsucc -> isleft == false) {
parent = xsucc;
xsucc = xsucc -> left;
}
x -> data = xsucc -> data;
x = xsucc;
}

/* if the node to be deleted has no child */

if ((x -> isleft == true) && (x -> isright == true)) {
       /* if node to be deleted is a root node */
if (parent == NULL) {
(*root) -> left = *root;
(*root) -> isleft = true;
FREE(x);
return;
}

if ( parent -> right == x ) {
parent -> isright = true;
parent -> right = x -> right;
} else {
parent -> isleft = true;
parent -> left = x -> left;
}
FREE(x);
return;
}

/* if the node to be deleted has only rightchild */

if ((x -> isleft == true) && (x -> isright == false)) {
/* node to be deleted is a root node */
if (parent == NULL) {
(*root) -> left = x -> right;
FREE(x);
return;
}

if (parent -> left == x) {
parent -> left = x -> right;
x -> right -> left = x -> left;
} else {
parent -> right = x -> right;
x -> right -> left = parent;
}
FREE(x);
return;
}

/* if the node to be deleted has only left child */

if ((x -> isleft == false) && (x -> isright == true)) {
/* the node to be deleted is a root node */
if (parent == NULL) {
parent = x;
xsucc = x -> left;
while (xsucc -> right == false)
xsucc = xsucc -> right;

xsucc -> right = *root;
(*root) -> left = x -> left;
FREE(x);
return;
}

if (parent -> left == x) {
parent -> left = x -> left;
x -> left -> right = parent;
} else {
parent -> right = x -> left;
x -> left -> right = x -> right;
}
FREE(x);
return;
}
}

/* returns address of node to be deleted, address of its parent and
    whether the node is found or not */

void search(thtree **root, int num, thtree **par, thtree **x, int *found)
{
thtree *q;

q = (*root) -> left;
*found = false;
*par = NULL;

while (q != *root) {
/* if the node to be deleted is found */
if (q -> data == num) {
*found = true;
*x = q;
return;
}

*par = q;
if (q -> data > num) {
if (q -> isleft == true) {
*found = false;
x = NULL;
return;
}
q = q -> left;
} else {
if (q -> isright == true) {
*found = false;
*x = NULL;
return;
}
q = q -> right;
}
}
}


/* traverses the threaded binary tree in inorder */
void inorder(thtree *root)
{
thtree *p;
p = root -> left;

while (p != root) {
while (p -> isleft == false)
p = p -> left;
printf ("%d\t", p -> data);

while (p -> isright == true) {
p = p -> right;
if (p == root)
break;
printf("%d\t", p -> data);
}
p = p -> right;
}
}