# Convert Sorted Array to Binary Search Tree Leetcode Solution  Difficulty Level Easy
algorithms Binary Search Tree coding Depth First Search Interview interviewprep LeetCode LeetCodeSolutions

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.

## 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:

1. Any node should have smaller elements as left children and vice versa for right children
2. 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 when the array is of an oddsize.

Find the Duplicate Element

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  1. Create another function converArrayToBST() which will convert any particular range of given array and return its corresponding BST root node.
2. Let L = left limit of array and R = right limit of array in the above-mentioned range.
1. If L > R
• return NULL, as we receive a wrong range
2. If L == R
• return a new node having value same as Array[L]
3. 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
3. 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);
head->left = convertArrayToBST(a , l , mid - 1);
head->right = convertArrayToBST(a , mid + 1 , r);
}

BSTNode* sortedArrayToBST(vector<int>& a)
{
int n = a.size();
return convertArrayToBST(a , 0 , n - 1);
}

{
return;
cout << head->value << " ";
}

int main()
{
vector <int> a = {-4 , 0 , 1 , 2 , 7};
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};
}

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);
head.left = convertArrayToBST(a , l , mid - 1);
head.right = convertArrayToBST(a , mid + 1 , r);
}

static BSTNode sortedArrayToBST(int[] a)
{
return convertArrayToBST(a , 0 , a.length - 1);
}

{
return;
}
}
```
`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.