How To Clone A BST Non Recursively In C Programming Language

Binary Search Tree

• BST[Binary Search Trees] is the data structure that will be in the form of a tree comprising of two nodes as child nodes for each node from the head node. 
• The trees are in such an order that whose value is less than the head node value will be placed towards left and value greater than head node value will be towards right node value, this way of placing values each after each level to child node also from head node onwards.

write a menu-driven program to create a binary search tree and perform the following non-recursive operations on it.

1. Copy a tree
2. Equality of two trees,
3. Delete a node from a tree

menu-driven:

menu-driven is a way of showing options that are available to the user in a menu form so that they can do what they want as per their wish present on the menu and this is done by using switch statement in programming language.

// write a menu-driven program to create a binary search tree//  and perform the following non recursive operations on it.
// 1. copy a tree,
// 2. Equality of two trees, 
// 3. Delete a node from a tree.

// header files
#include <stdio .h>
#include <stdlib .h>

// Node Structures
struct node {
    int data;
    struct node *right;
    struct node *left;
};

// Queue
struct Queue
{
    int front, rear, size;
    int capacity;
    struct node * *array;
};
typedef struct Queue queue;
queue* createQueue(int capacity)
{
    queue* qu =(queue*)malloc(sizeof(queue));
    qu->capacity = capacity;
    qu->front = qu->size =0;
    qu->rear = capacity-1;
    qu->array = (struct node **)malloc(qu->capacity * sizeof(struct node));
    return qu;
}
int isQFull(queue*  queue1)
{
    return (queue1->size == queue1->capacity);
}
int isQEmpty(queue* queue1)
{
    return (queue1->size==0);
}
void enqueue(queue* queue1, struct node* item)
{
    if(isQFull(queue1))
        return ;
    queue1->rear = (queue1->rear +1 )%queue1->capacity;
    queue1->array[queue1->rear] = item;
    queue1->size = queue1->size +1;

}
struct node* dequeue(queue* queue1)
{
    struct node* item = queue1->array[queue1->front];
    queue1->front = (queue1->front +1)%queue1->capacity;
    queue1->size = queue1->size -1;
    return item;
}
struct node* front(queue* queue1)
{
    return queue1->array[queue1->front];
}
struct node* rear(queue * queue1)
{
    return queue1->array[queue1->rear];
}

// PROTYPES
struct node *copy_a_tree(struct node *root); // Copy a tree
struct node *delete(struct node *root,int data); // Deletee a node from the tree
struct node *insert(struct node *root,int data); // Insert a node into the tree 
struct node *min(struct node *root); // Find the minimum node
struct node* newNode(int data) ; //create a new node
void display(struct node *root, int level); // Display binary tree in order
int equality_of_two_tree(struct node *root,struct node *one); // Equality of two tree
void inorder(struct node *root); // Inorder Traversal
void postorder(struct node *root); // Postorder Traversal
void preorder(struct node *root); // Preorder Traversal
void levelOrderTraversal(struct node *root); // level order traversal


void main(void)
{
    struct node *root = NULL,*one = NULL;
    int operationNumber, data;

    while(1) 
    {
        printf("\nList of the operations are:\n"
                "1. Insert a node into the tree\n"
                "2. Delete the node from the tree\n"
                "3. PreOrder Traversal\n"
                "4. PostOrder Traversal\n"
                "5. Inorder Traversal\n"
                "6. Copy the tree\n"
                "7. Equality of two tree \n"
                "8. Display tree\n"
                "9. Exit the code\n");

        printf("\nPlease enter the operation number you want to perform: ");
        scanf("%d", &operationNumber);

        // Menu Driven Code
        switch(operationNumber)
        {
            case 1: printf("\nEnter the key to be inserted: ");
                    scanf("%d",&data);
                    root = insert(root,data);
                    break;

            case 2: printf("Enter the key to be deleted: ");
                    scanf("%d",&data);
                    root = delete(root,data); 
                    break;

            case 3: printf("\nPreorder Traversal is: ");
                    preorder(root); 
                    break;

            case 4: printf("\nPostorder Traversal is: ");
                    postorder(root);
                    printf("\n");
                    break;

            case 5: printf("\nInorder Traversal is: ");
                    inorder(root);
                    printf("\n");
                    break;

            case 6: printf("\ncopy of tree is: \n");
                    one = copy_a_tree(root);
                    printf("\n");
                    break;

            case 7: printf("\nEquality of two tree:");
                    if(equality_of_two_tree(root,one))
                        printf("\nBoth trees are equal and identical\n");
                    else
                        printf("\nTrees are not equal and identical\n");
                    break;

            case 8:printf("\nTree display:");
                    display(root,0);
                    break;

            case 9: exit(0);
                    break;
            default: printf("\nWrong Choise\n");
        } // end switch
    } // end while
}// end main()

// Function to create a new node
 struct node* newNode(int data) 
 {
  /* dynamically allocate memory for a new node */
  struct node* node = (struct node*)malloc(sizeof(struct node));
  
  /* populate data in new Node */
  node->data = data;
  node->left = node->right = NULL;
  return node;
}// end newNode()

// Function to find the min value
struct node *min(struct node*root)
{
	if (root == 0)
		return 0;

	else if (root->left != 0)
		return min(root->left);
	return root;
}// end min()

// Displat the tree
void display(struct node *root, int level)
{
    if (root == NULL) 
        return ;
    else
    {
        display(root->right, level+1);
        printf("\n");
        for (int i = 0; i < level; i++)
            printf("\t\t");
        printf("%d",root->data);
        display(root->left, level+1);
    } 
} // end display()

// Insert a node into the tree 
struct node *insert(struct node *root,int data)
{
    struct node *par,*ptr;
    ptr=root;
    par=NULL;

    while(ptr!=NULL)
    {
        par=ptr;
        if(data < ptr->data)
            ptr=ptr->left;
        else if(data > ptr->data)
            ptr=ptr->right;
        else 
            return root;
    }
    if (root == NULL)
	{
		root = (struct node *)malloc(sizeof(struct node));
		root->data = data;
		root->left = root->right = NULL;
	}

	else if (data < root->data)
		root->left = insert(root->left, data);

	else if (data > root->data)
		root->right = insert(root->right, data);

	else
		printf("%d", data , " is already present in the tree\n");

	return root;
}// end insert()

// Deletee a node from the tree
struct node *delete(struct node *root,int data)
{
    if (root == NULL)
	{
		printf("the element is not found \n");
		return root;
	} 

    // primary level check for element
	if (data < root->data)
		root->left = delete(root->left, data);

	else if (data > root->data)
		root->right = delete(root->right, data);
    // Secondary level check for element
	else
	{
		if (root->left == NULL)
		{
			struct node *temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL)
		{
			struct node *temp = root->left;
			free(root);
			return temp;
		}
		struct node *temp = min(root->right);
		root->data = temp->data;

		root->right = delete(root->right, temp->data);
	}// end else
	return root;
} // end delete()

// Preorder Traversal
void preorder(struct node *root)
{
    if (root)
	{
		printf(" %d ",root->data);
		preorder(root->left);
		preorder(root->right);
	}
} // end preorder()

// Postorder Traversal
void postorder(struct node *root)
{
    if (root)
	{
		postorder(root->left);
		postorder(root->right);
		printf(" %d ",root->data);
	}
} // end postOrderTraversal

// Inorder Traversal
void inorder(struct node *root)
{
    if (root)
	{
		inorder(root->left);
		printf(" %d ",root->data);
		inorder(root->right);
	}
} // end inorder()

// level order traversal
void levelOrderTraversal(struct node *root)
{
    if (root == NULL)
        return;
    queue* q = createQueue(100000);
    enqueue(q,root);
    while (!isQEmpty(q))
    {
        struct node *t = front(q);
        printf("%d ",t->data);
        dequeue(q);

        if (t->left != NULL)
            enqueue(q,t->left);

        if (t->right != NULL)
            enqueue(q,t->right);
    }

}
// Equality of two tree
int equality_of_two_tree(struct node *one,struct node *two)
{
    /*1. both empty */
    if (one==NULL && two==NULL)
     return 1;
    
    /* 2. both non-empty -> compare them */
    if (one!=NULL && two!=NULL)
    {
        return
        (
            one->data == two->data &&
            equality_of_two_tree(one->left, two->left) &&
            equality_of_two_tree(one->right, two->right)
        );
    }
    /* 3. one empty, one not -> false */
    return 0;
} // end equality_of_two_tree()

// Copy a tree
struct node *copy_a_tree(struct node *root)
{
    if(root == NULL)
        return NULL;
    
    struct node *root2;
    queue* q = createQueue(100000);
    enqueue(q,root);
    root2 = newNode(root->data);
    while (!isQEmpty(q))
    {
        struct node *t = front(q);
        dequeue(q);
        if (t->left != NULL)
        {
            enqueue(q,t->left);
            insert(root2, t->left->data);
        }

        if (t->right != NULL)
        {
            enqueue(q,t->right);
            insert(root2,t->right->data);
        }

    }
    levelOrderTraversal(root2);
    return root2;
    
    // Recursive solution
    // /* create a copy of root node */
    // struct node* new = newNode(root->data);
    // /* Recursively create clone of left and right sub tree */
    // new->left = copy_a_tree(root->left);
    // new->right = copy_a_tree(root->right);
    // printf("%d ",root->data);
    // /* Return root of cloned tree */
    // return new;

} // end copy_a_tree()