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

advertisement
advertisement
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.

  1. /* C Program to convert given binary tree to BST */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. struct node
  7. {
  8.     int info;
  9.     struct node* left, *right;
  10. };
  11.  
  12. int data[100];
  13. int i = 0;
  14.  
  15. /*creates a new node */
  16.  
  17. struct node* createnode(int key)
  18. {
  19.     struct node* newnode = (struct node*)malloc(sizeof(struct node));
  20.     newnode->info = key;
  21.     newnode->left = NULL;
  22.     newnode->right = NULL;
  23.  
  24.     return(newnode);
  25. }
  26.  
  27. /* counts the number of nodes in a tree */
  28.  
  29. int count(struct node *n)
  30. {
  31.     int c = 1;
  32.  
  33.     if (n == NULL)
  34.         return 0;
  35.     else
  36.     {
  37.         c += count(n->left);
  38.         c += count(n->right);
  39.         return c;
  40.     }
  41. }
  42.  
  43. /*
  44.  * Copies the nodes of Binary Tree in an array
  45.  */
  46. void binarytoarray(struct node * root, int data[], int *ptr)
  47. {
  48.     if(root != NULL)
  49.     {
  50.     binarytoarray(root->left, data, ptr);
  51.     data[*ptr] = root->info;
  52.     (*ptr)++;
  53.     binarytoarray(root->right, data, ptr);
  54.     }
  55. }
  56.  
  57. /*
  58.  * Copies the element of array to bst
  59.  */
  60. void arraytobst(int *arr, struct node *root, int *index)
  61. {
  62.     if(root != NULL)
  63.     {
  64.         arraytobst(arr, root->left, index);
  65.         root->info = arr[i++];
  66.         arraytobst(arr, root->right, index);
  67.     }
  68. }
  69.  
  70. int compare(const void *a, const void *b)
  71. {
  72.     return *(int*)a-*(int*)b;
  73. }
  74.  
  75. /*
  76.  * Inorder traversal of a tree
  77.  */
  78.  
  79. void inorder(struct node *root)
  80. {
  81.     if(root !=NULL)
  82.     {
  83.         inorder(root->left);
  84.         printf("%d\t",root->info);
  85.         inorder(root->right);
  86.     }
  87. }
  88.  
  89. /*
  90.  * Converts binary tree to bst
  91.  */
  92. void binary_to_bst(struct node *root)
  93. {
  94.     int n, i;
  95.  
  96.     if (root == NULL)
  97.         return;
  98.     n = count(root);
  99.     i = 0;
  100.     binarytoarray(root, data, &i);
  101.     qsort(&data, n, sizeof(data[0]), compare);
  102.     i = 0;
  103.     arraytobst(data, root, &i);
  104. }
  105.  
  106. /*
  107.  * Main Function
  108.  */
  109.  
  110. int main()
  111. {
  112.     int flag = 0;
  113.     struct node *newnode = createnode(25);
  114.     newnode->left = createnode(27);
  115.     newnode->right = createnode(19);
  116.     newnode->left->left = createnode(17);
  117.     newnode->left->right = createnode(91);
  118.     newnode->right->left = createnode(13);
  119.     newnode->right->right = createnode(55);
  120.  
  121.     /* Sample Tree 1- Balanced Tree
  122.  
  123.  
  124.                     25                   |          25   
  125.                   /    \                 |        /    \
  126.                  27     19               |       17      55
  127.                 / \     / \              |      /  \    /  \
  128.               17  91   13 55             |    13   19  27   91
  129.  
  130.     */
  131.  
  132.     printf("Inorder traversal of Input Binary Tree is\n");
  133.     inorder(newnode);
  134.     binary_to_bst(newnode);
  135.     printf("\nInorder traversal of the converted Binary Search Tree is\n");
  136.     inorder(newnode);
  137.     return 0;
  138. }
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.

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.

advertisement

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.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.