ronith
9/7/2018 - 4:48 PM

Sorted Array to Balanced BST

Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements.

Examples:

Input: Array {1, 2, 3} Output: A Balanced BST 2 /
1 3

Input: Array {1, 2, 3, 4} Output: A Balanced BST 3 /
2 4 / 1

Sorted Array to Balanced BST.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
#include <iostream>
using namespace std;

struct node {
    int data;
    struct node* left;
    struct node* right;
};

node* bst (int a[], int l, int r) {
    if (l>r)
        return NULL;

    int m= (l+r)/2;
    node *head= (node*)malloc(sizeof(node));
    head->data= a[m];
    head->left = bst(a, l, m-1);
    head->right = bst(a, m+1, r);

    return head;
}

void preOrder(node *head) {
    if (head==NULL)
        return;
    cout<< head->data << " ";
    preOrder(head->left);
    preOrder(head->right);
}

int main() {
    int t;
    cin>>t;
    while (t-->0) {
        int n;
        cin>>n;
        int a[n];
        for (int i=0;i<n;i++)
            cin>>a[i];

        node* head= bst(a,0, n-1);
        preOrder(head);
    }
}