Consider we are given a sorted array of integers. The goal is to build a Binary Search Tree from this array such that the tree is height-balanced. Note that a tree is said to be height-balanced if the height difference of left and right subtrees of any node in the tree is at most 1.

It is easy to find that there can be multiple solutions. We need to find any valid solution. Note that in this problem, we do not need to print the tree but to create one. We just need to print its preorder traversal.

Table of Contents

## Example

Array = {-4 , 0 , 1 , 2 , 7}

1 -4 0 2 7

Explanation: The BST is:

Array = {1 , 2 , 3}

2 1 3

Explanation: The BST is:

## Approach(Recursion)

We need to keep track of two things:

- Any node should have smaller elements as left children and vice versa for right children
- The BST should be Height Balanced

In order to keep the tree balanced at any moment, we must choose a middle element of the array as the root. In this way, we will have a height difference of **1 **between the left and right subtrees if the array is of even size and a height difference of **0 **when the array is of an oddsize.

Now, when we select any middle node as root, we have to create the left subtree from the left subarray and right subtree from the right subarray. This is a sub-problem of our original problem and hence we can solve it recursively. After assigning left and right subtree to the middle node, we can return it and print the postorder traversal of the Binary Search Tree.

## Algorithm

- Create another function
**converArrayToBST()**which will convert any particular range of given array and return its corresponding BST root node. - Let L = left limit of array and R = right limit of array in the above-mentioned range.
- If L > R
- return
**NULL**, as we receive a wrong range

- return
- If L == R
- return a new node having value same as
**Array[L]**

- return a new node having value same as
- Find the middle node of this range as
**mid = (L + (R – L) / 2)**- Initialise head as a new BST Node with value same as
**Array[mid]** - Assign
**left**and**right**subtrees as the same function called on left and right sub-ranges respectively - Return head

- Initialise head as a new BST Node with value same as

- If L > R
- Print the preorder traversal of the Binary Search Tree

## Implementation of Convert Sorted Array to Binary Search Tree Leetcode Solution

### C++ Solution to Convert Sorted Array to Binary Search Tree

#include <bits/stdc++.h> using namespace std; struct BSTNode { int value; BSTNode *left , *right; BSTNode(int x) { value = x; left = NULL; right = NULL; } }; BSTNode* convertArrayToBST(vector <int> &a , int l , int r) { if(l > r) return NULL; if(l == r) return new BSTNode(a[l]); int mid = (l + (r - l) / 2); BSTNode* head = new BSTNode(a[mid]); head->left = convertArrayToBST(a , l , mid - 1); head->right = convertArrayToBST(a , mid + 1 , r); return head; } BSTNode* sortedArrayToBST(vector<int>& a) { int n = a.size(); return convertArrayToBST(a , 0 , n - 1); } void preorder(BSTNode* head) { if(!head) return; cout << head->value << " "; preorder(head->left); preorder(head->right); } int main() { vector <int> a = {-4 , 0 , 1 , 2 , 7}; BSTNode* head = sortedArrayToBST(a); preorder(head); return 0; }

### Java Solution to Convert Sorted Array to Binary Search Tree

class BSTNode { int value; BSTNode left , right; BSTNode(int x) { value = x; left = null; right = null; } } class convert_array_to_BST { public static void main(String args[]) { int[] a = {-4 , 0 , 1 , 2 , 7}; BSTNode head = sortedArrayToBST(a); preorder(head); } static BSTNode convertArrayToBST(int[] a , int l , int r) { if(l > r) return null; if(l == r) return new BSTNode(a[l]); int mid = (l + (r - l) / 2); BSTNode head = new BSTNode(a[mid]); head.left = convertArrayToBST(a , l , mid - 1); head.right = convertArrayToBST(a , mid + 1 , r); return head; } static BSTNode sortedArrayToBST(int[] a) { return convertArrayToBST(a , 0 , a.length - 1); } static void preorder(BSTNode head) { if(head == null) return; System.out.print(head.value + " "); preorder(head.left); preorder(head.right); } }

1 -4 0 2 7

## Complexity Analysis of Convert Sorted Array to Binary Search Tree Leetcode Solution

### Time Complexity

**O(N), **N = Number of elements in the tree. We visit every element to construct the BST and to print the preorder traversal.

### Space Complexity

**O(H), **where H = Height of the tree = **logN. **In both the recursive functions, we make sure that the tree is height-balanced, So, we use a maximum of **O(H) **space for recursive stack frames.