C Program to Convert Doubly Linked List to Balanced BST

This C Program creates a balanced binary search tree which has same data members as the given Doubly linked list by changing the pointers internally.

Here is a source code of the C program to create a balanced binary search tree which has same data members as that of a doubly linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to Construct a Balanced Binary Search Tree

 * which has same data members as the given Doubly Linked List

```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int num;
```
```
    struct node *left;
```
```
    struct node *right;
```
```
};
```
```
 
```
```
void create(struct node **);
```
```
void treemaker(struct node **, int);
```
```
void display(struct node *);
```
```
void displayTree(struct node *);
```
```
void delete(struct node **);
```
```
 
```
```
int main()
```
```
{
```

    struct node *headList = NULL, *rootTree, *p;

```
    int count = 1, flag = 0;
```
```
 
```
```
    create(&headList);
```

    printf("Displaying the doubly linked list:\n");

```
    display(headList);
```
```
    rootTree = p = headList;
```
```
    while (p->right != NULL)
```
```
    {
```
```
        p = p->right;
```
```
        count = count + 1;
```
```
        if (flag)
```
```
        {
```
```
            rootTree = rootTree->right;
```
```
        }
```
```
        flag = !flag;
```
```
    }
```
```
    treemaker(&rootTree, count / 2);
```

    printf("Displaying the tree: (Inorder)\n");

```
    displayTree(rootTree);
```
```
    printf("\n");
```
```
 
```
```
    return 0;
```
```
}
```
```
 
```
```
void create(struct node **head)
```
```
{
```
```
    struct node *rear, *temp;
```
```
    int a, ch;
```
```
 
```
```
    do
```
```
    {
```
```
        printf("Enter a number: ");
```
```
        scanf("%d", &a);
```

        temp = (struct node *)malloc(sizeof(struct node));

```
        temp->num = a;
```
```
        temp->right = NULL;
```
```
        temp->left = NULL;
```
```
        if (*head == NULL)
```
```
        {
```
```
            *head = temp;
```
```
        }
```
```
        else
```
```
        {
```
```
            rear->right = temp;
```
```
            temp->left = rear;
```
```
        }
```
```
        rear = temp;
```

        printf("Do you wish to continue [1/0] ?: ");

```
        scanf("%d", &ch);
```
```
    } while (ch != 0);
```
```
}
```
```
 
```

void treemaker(struct node **root, int count)

```
{
```

    struct node *quarter, *thirdquarter;

```
    int n = count, i = 0;
```
```
 
```
```
    if ((*root)->left != NULL)
```
```
    {
```
```
        quarter = (*root)->left;
```

        for (i = 1; (i < count / 2) && (quarter->left != NULL); i++)

```
        {
```
```
            quarter = quarter->left;
```
```
        }
```
```
        (*root)->left->right = NULL;
```
```
        (*root)->left = quarter;
```
```
        /*
```

         * Uncomment the following line to see when the pointer changes

```
         */
```

        //printf("%d's left child is now %d\n", (*root)->num, quarter->num);

```
        if (quarter != NULL)
```
```
        {
```

            treemaker(&quarter, count / 2);

```
        }
```
```
    }
```
```
    if ((*root)->right != NULL)
```
```
    {
```
```
        thirdquarter = (*root)->right;
```

        for (i = 1; (i < count / 2) && (thirdquarter->right != NULL); i++)

```
        {
```

            thirdquarter = thirdquarter->right;

```
        }
```
```
        (*root)->right->left = NULL;
```
```
        (*root)->right = thirdquarter;
```
```
        /*
```

         * Uncomment the following line to see when the pointer changes

```
         */
```

        //printf("%d's right child is now %d\n", (*root)->num, thirdquarter->num);

```
        if (thirdquarter != NULL)
```
```
        {
```

            treemaker(&thirdquarter, count / 2);

```
        }
```
```
    }
```
```
}
```
```
 
```
```
void display(struct node *head)
```
```
{
```
```
    while (head != NULL)
```
```
    {
```
```
        printf("%d  ", head->num);
```
```
        head = head->right;
```
```
    }
```
```
    printf("\n");
```
```
}
```
```
 
```

/*DisplayTree performs inorder traversal*/

```
void displayTree(struct node *root)
```
```
{
```
```
    if (root != NULL)
```
```
    {
```
```
        displayTree(root->left);
```
```
        printf("%d  ", root->num);
```
```
        displayTree(root->right);
```
```
    }
```
```
}
```
```
 
```
```
void delete(struct node **root)
```
```
{
```
```
    if (*root != NULL)
```
```
    {
```
```
        displayTree((*root)->left);
```
```
        displayTree((*root)->right);
```
```
        free(*root);
```
```
    }
```
```
}
```

$ gcc doublytotree.c
$ ./a.out 
Enter a number: 1
Do you wish to continue [1/0] ?: 1
Enter a number: 2
Do you wish to continue [1/0] ?: 1
Enter a number: 3
Do you wish to continue [1/0] ?: 1
Enter a number: 4
Do you wish to continue [1/0] ?: 1
Enter a number: 5
Do you wish to continue [1/0] ?: 1
Enter a number: 6
Do you wish to continue [1/0] ?: 0
Displaying the doubly linked list:
1  2  3  4  5  6  
Displaying the tree: (Inorder)
1  2  3  4  5  6