This program demonstrates how to convert a sorted array into a balanced Binary Search Tree (BST). A balanced BST ensures that operations like search, insert, and delete are efficient.

Program Explanation

The program consists of:

• Node Structure: Defines the structure of a BST node.
• Utility Function to Create a Node: Allocates memory for a new node and initializes it.
• Recursive Function to Build BST: This function takes the sorted array and recursively builds a balanced BST.
• Main Function: The driver function to invoke the creation of BST and to print the BST in order (to verify correctness).

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>

// Define the structure for BST nodes
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Recursive function to convert sorted array to BST
Node* sortedArrayToBST(int arr[], int start, int end) {
    // Base case
    if (start > end)
        return NULL;

    // Get the middle element and make it root
    int mid = (start + end) / 2;
    Node* root = createNode(arr[mid]);

    // Recursively construct the left subtree
    root->left = sortedArrayToBST(arr, start, mid - 1);

    // Recursively construct the right subtree
    root->right = sortedArrayToBST(arr, mid + 1, end);

    return root;
}

// A utility function to print in-order traversal of the BST
void printInOrder(Node* node) {
    if (node != NULL) {
        printInOrder(node->left);
        printf("%d ", node->data);
        printInOrder(node->right);
    }
}

// Main function
int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* root = sortedArrayToBST(arr, 0, n - 1);

    printf("In-order traversal of the constructed BST: ");
    printInOrder(root);
    printf("\\n");

    return 0;
}
    

Key Components of the Program:

• Node Structure: Defines a node in the BST, containing data, and pointers to left and right children.
• createNode Function: Allocates and initializes a new node with the given data.
• sortedArrayToBST Function: This recursive function is the core of the program. It selects the middle element of the array to ensure the BST is balanced. The function then recursively builds the left and right subtrees using the same logic.
• printInOrder Function: To verify the correctness of the tree’s structure, this function prints the nodes in an in-order traversal, which should display the original sorted array.
• Main Function: Sets up the sorted array, calls the sortedArrayToBST function to construct the BST, and prints the BST using in-order traversal.

This program structure is straightforward yet powerful, ensuring that the tree remains balanced, thus optimizing the performance of various BST operations.