C Program to Convert Binary Tree to Binary Search Tree

This is a C Program for conversion of Binary Tree to Binary Search Tree.

Problem Description

We will be given a Binary Tree as input and we have to convert it into a Binary Search Tree using C Language.

Expected Input and Output

Case 1. Balanced Tree

 
                    25                   |          25   
                  /    \                 |        /    \
                 27     19               |       17     55
                / \     / \              |      /  \    / \
              17  91   13 55             |    13   19  27  91
 
                 Binary Tree                  Binary Search Tree

Output:

Inorder traversal of Binary Tree is 17 27 91 25 13 19 55
Inorder traversal of Binary Search Tree 13 17 19 25 27 55 91

Problem Solution

1. In order to convert a Binary Tree to a Binary Search Tree, we should know that the inorder traversal of a Binary Search Tree stored in an array will be a sorted array in ascending order.
2. We just need to store the inorder traversal of a Binary Tree in an array and then sort it.
3. After sorting the array, we need to store the array values one by one to nodes of BST, starting from the extreme left.
4. At last, we will do the inorder traversal of the converted Binary Search Tree.

Program/Source Code

Here is source code of the C Program for conversion of Binary Tree to a Binary Search Tree. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on windows 10. The program output is also shown below.

/* C Program to convert given binary tree to BST */

```
 
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node* left, *right;
```
```
};
```
```
 
```
```
int data[100];
```
```
int i = 0;
```
```
 
```
```
/*creates a new node */
```
```
 
```
```
struct node* createnode(int key)
```
```
{
```

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

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
 
```
```
    return(newnode);
```
```
}
```
```
 
```

/* counts the number of nodes in a tree */

```
 
```
```
int count(struct node *n)
```
```
{
```
```
    int c = 1;
```
```
 
```
```
    if (n == NULL)
```
```
        return 0;
```
```
    else
```
```
    {
```
```
        c += count(n->left);
```
```
        c += count(n->right);
```
```
        return c;
```
```
    }
```
```
}
```
```
 
```
```
/*
```

 * Copies the nodes of Binary Tree in an array

```
 */
```

void binarytoarray(struct node * root, int data[], int *ptr)

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

    binarytoarray(root->left, data, ptr);

```
    data[*ptr] = root->info;
```
```
    (*ptr)++;
```

    binarytoarray(root->right, data, ptr);

```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Copies the element of array to bst
```
```
 */
```

void arraytobst(int *arr, struct node *root, int *index)

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

        arraytobst(arr, root->left, index);

```
        root->info = arr[i++];
```

        arraytobst(arr, root->right, index);

```
    }
```
```
}
```
```
 
```

int compare(const void *a, const void *b)

```
{
```
```
    return *(int*)a-*(int*)b;
```
```
}
```
```
 
```
```
/*
```
```
 * Inorder traversal of a tree
```
```
 */
```
```
 
```
```
void inorder(struct node *root)
```
```
{
```
```
    if(root !=NULL)
```
```
    {
```
```
        inorder(root->left);
```
```
        printf("%d\t",root->info);
```
```
        inorder(root->right);
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Converts binary tree to bst
```
```
 */
```
```
void binary_to_bst(struct node *root)
```
```
{
```
```
    int n, i;
```
```
 
```
```
    if (root == NULL)
```
```
        return;
```
```
    n = count(root);
```
```
    i = 0;
```
```
    binarytoarray(root, data, &i);
```

    qsort(&data, n, sizeof(data[0]), compare);

```
    i = 0;
```
```
    arraytobst(data, root, &i);
```
```
}
```
```
 
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
 
```
```
int main()
```
```
{
```
```
    int flag = 0;
```

    struct node *newnode = createnode(25);

```
    newnode->left = createnode(27);
```
```
    newnode->right = createnode(19);
```

    newnode->left->left = createnode(17);

    newnode->left->right = createnode(91);

    newnode->right->left = createnode(13);

    newnode->right->right = createnode(55);

```
 
```
```
    /* Sample Tree 1- Balanced Tree
```
```
 
```
```
 
```

                    25                   |          25

                  /    \                 |        /    \

                 27     19               |       17      55

                / \     / \              |      /  \    /  \

              17  91   13 55             |    13   19  27   91

```
 
```
```
    */
```
```
 
```

    printf("Inorder traversal of Input Binary Tree is\n");

```
    inorder(newnode);
```
```
    binary_to_bst(newnode);
```

    printf("\nInorder traversal of the converted Binary Search Tree is\n");

```
    inorder(newnode);
```
```
    return 0;
```
```
}
```

Program Explanation

1. To convert a Binary Tree to a Binary Search Tree, we need to know that the inorder traversal of a BST gives an array of numbers sorted in ascending order.
2. Using function binarytoarray() we have stored the inorder traversal of input Binary Tree, and then sorted that array using a Sorting Method. After Sorting the array we have traversed the tree again using inorder traversal, but this time we update the values of the nodes in a tree.
3. After traversing and updating the whole tree, the final tree which we will obtain will be a Binary Search Tree, whose inorder traversal will be a series of numbers listed in ascending order.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

Runtime Test Cases

 
Inorder traversal of Input Binary Tree is
17      27      91      25      13      19      55
Inorder traversal of the converted Binary Search Tree is
13      17      19      25      27      55      91

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

« Prev - C Program to Find the Nearest Common Ancestor

» Next - C Program to Find the Total Columns/Vertical Lines of a Binary Search Tree

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Programming MCQs
Practice Computer Science MCQs
Check Programming Books

Recommended Articles: