[Solved] Complete Binary Tree and Traversals with C

Implement a C program to construct a Complete Binary Tree and also display the elements in the tree using Inorder , Preorder and Postorder traversals.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Consider the following structure to create a binary tree

struct tree
{
    int data;
    struct tree *right,*left;
};

struct queue
{
    int front, rear;
    int size;
    struct tree* *array;
};

Function Specifications:

struct tree* newNode(int data)
struct queue* createQueue(int size)
void enqueue(struct tree *root, struct queue* queue)
struct tree* dequeue(struct queue* queue)
void insert(struct tree **root, int data, struct queue* queue)
void inorder(struct tree *)
void preorder(struct tree *)
void postorder(struct tree *)

Input and Output Format:

Refer Sample Input and Output for formatting specifications.

[All text in bold corresponds to input and the rest corresponds to output]

Sample Input and Output:

Enter the element to be inserted in the tree

1

Do you want to insert another element?

yes

Enter the element to be inserted in the tree

2

Do you want to insert another element?

yes

Enter the element to be inserted in the tree

3

Do you want to insert another element?

yes

Enter the element to be inserted in the tree

4

Do you want to insert another element?

yes

Enter the element to be inserted in the tree

5

Do you want to insert another element?

yes

Enter the element to be inserted in the tree

6

Do you want to insert another element?

yes

Enter the element to be inserted in the tree

7

Do you want to insert another element?

yes

Enter the element to be inserted in the tree

8

Do you want to insert another element?

no

Inorder Traversal : The elements in the tree are 8 4 2 5 1 6 3 7

Preorder Traversal : The elements in the tree are 1 2 4 8 5 3 6 7

Postorder Traversal : The elements in the tree are 8 4 5 2 6 7 3 1

Function Definitions:

void inorder (struct tree *)

void preorder (struct tree *)

void  postorder (struct tree *)

Solution

#include <stdio.h>
#include <stdlib.h>
#include<string.h>

struct tree{
    int data;
    struct tree *right,*left;
};

struct queue{
    int front, rear;
    int size;
    struct tree* *array;
};

struct tree* newNode(int data);
struct queue* createQueue(int size);
void enqueue(struct tree *root, struct queue* queue);
struct tree* dequeue(struct queue* queue);
void insert(struct tree **root, int data, struct queue* queue);
void inorder(struct tree *);
void preorder(struct tree *);
void postorder(struct tree *);
  
int main()
{
    struct tree* root = NULL;
  char ans[3];
  int data;
    struct queue* queue = createQueue(100);
 do
 {
  printf("Enter the element to be inserted in the tree\n");
            scanf("%d",&data);          
        insert(&root, data, queue);
    printf("Do you want to insert another element?\n");
              scanf("%s",ans);
         } while (strcmp(ans,"yes") ==0); 
 
 printf("Inorder Traversal : The elements in the tree are");
            inorder(root);
            printf("\n");
            printf("Preorder Traversal : The elements in the tree are");
            preorder(root);
   printf("\n");
            printf("Postorder Traversal : The elements in the tree are");
            postorder(root);
      return 0;
}

struct tree* newNode(int data) {
    struct tree *nn = (struct tree*)malloc(sizeof(struct tree));
    nn->data = data;
    nn->right = nn->left = NULL;
    return nn;
}

struct queue* createQueue(int size){
    struct queue *nn = (struct queue*)malloc(sizeof(struct queue));
    nn->front = -1;
    nn->rear = 0;
    nn->size = size;
    nn->array = (struct tree**)malloc(size * sizeof(struct tree*));
    return nn;
}

int isEmpty(struct queue* q){
        return (q->front == -1 || q->rear == q->front);
}

struct tree* enquire(struct queue* nn){
    return nn->array[nn->rear];
}

void insert(struct tree **root, int data, struct queue* q){
    struct tree* nn = (struct tree*)malloc(sizeof(struct tree));
    nn->data = data;
    nn->left = nn->right = NULL;
    enqueue(nn,q);
    
    if(isEmpty(q) && !(*root)){
        *root = nn;
    }
    else if(!(enquire(q)->left)){
        enquire(q)->left = nn;
    }else if(!(enquire(q)->right)){
        enquire(q)->right = nn;
        dequeue(q);
    }
}

void enqueue(struct tree *root, struct queue* nn){
    nn->front = (nn->front + 1) % nn->size; 
    nn->array[nn->front] = root;
}
 

struct tree* dequeue(struct queue* nn){
    struct tree* temp = nn->array[nn->rear];
    nn->rear = (nn->rear + 1) % nn->size;
    return temp;
}

void inorder(struct tree *temp) {
    if(temp){
        inorder(temp->left);
        printf(" %d",temp->data);
        inorder(temp->right);
    }
}

void preorder(struct tree *temp) {
    if(temp){
        printf(" %d",temp->data);
        preorder(temp->left);
        preorder(temp->right);
    }
}
 

void postorder(struct tree *temp) {
    if(temp){
        postorder(temp->left);
        postorder(temp->right);
        printf(" %d",temp->data);
    }
}

Happy Learning – If you require any further information, feel free to contact me.