C Program to Convert Sorted Array to Balanced BST

This C Program Construct a Balanced Binary Tree using Sorted Array.

Here is source code of the C Program to Construct a Balanced Binary Tree using Sorted Array. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to Construct a Balenced Binary Tree using Sorted Array

```
 *                   40
```
```
 *                   /  \
```
```
 *                  20   60
```
```
 *                 /  \   \
```
```
 *                10  30   80
```
```
 *                          \
```
```
 *                           90    
```

 *            (Given Binary Search Tree)

```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h> 
```
```
 
```
```
struct btnode
```
```
{
```
```
    int value;
```
```
    struct btnode *l;
```
```
    struct btnode *r;
```
```
};
```
```
 
```
```
typedef struct btnode N;
```
```
N* bst(int arr[], int first, int last);
```
```
N* new(int val);
```
```
void display(N *temp);
```
```
 
```
```
int main()
```
```
{   
```

    int arr[] = {10, 20, 30, 40, 60, 80, 90};

```
    N *root = (N*)malloc(sizeof(N));  
```

    int n = sizeof(arr) / sizeof(arr[0]), i;

```
 
```
```
    printf("Given sorted array is\n");
```
```
    for (i = 0;i < n;i++)
```
```
        printf("%d\t", arr[i]);
```
```
    root = bst(arr, 0, n - 1); 
```

    printf("\n The preorder traversal of binary search tree is as follows\n");

```
    display(root);
```
```
    printf("\n");   
```
```
    return 0;
```
```
}
```
```
 
```
```
/* To create a new node */
```
```
N* new(int val)
```
```
{
```
```
    N* node = (N*)malloc(sizeof(N));
```
```
 
```
```
    node->value = val;
```
```
    node->l = NULL;
```
```
    node->r  =  NULL;
```
```
    return node;
```
```
}
```
```
 
```

/* To create a balanced binary search tree */

```
N* bst(int arr[], int first, int last)
```
```
{
```
```
    int mid;
```
```
    N* temp = (N*)malloc(sizeof(N));
```
```
    if (first > last)
```
```
        return NULL;
```
```
    mid = (first + last) / 2;
```
```
    temp = new(arr[mid]);
```
```
    temp->l = bst(arr, first, mid - 1);
```
```
    temp->r = bst(arr, mid + 1, last);
```
```
    return temp;
```
```
}
```
```
 
```
```
/* To display the preorder */
```
```
void display(N *temp)
```
```
{
```
```
    printf("%d->", temp->value);
```
```
    if (temp->l != NULL)
```
```
        display(temp->l);
```
```
    if (temp->r != NULL)
```
```
        display(temp->r);
```
```
}
```

$ cc tree21.c
$ a.out
Given sorted array is
10      20      30      40      60      80      90
The preorder traversal of binary search tree is as follows
40->20->10->30->80->60->90

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.

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

« Prev - C Program to Add Corresponding Positioned Elements of Two Linked Lists

» Next - C Program to Find the Common Ancestor and Path

Related Posts:

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

Recommended Articles: