Given an array **A[] **of size **N**, sorted in ascending order. The task is to convert it into balanced **BST**.

A balanced BST is a binary tree in which the height of the left subtree and right subtree is not more than **one.**

**Examples:**

## Approach: Recursive Solution

Since the array is **sorted, **taking advantage of this fact, the idea is to build the tree by dividing the array into **two parts**.

Let us consider the index as **mid**, where the array has been divided.

### Confused about your next job?

Since in a binary search tree, the elements to the left of a node are smaller and elements to the right are greater. Similarly, to construct the tree, the element to the left of mid would consist of the left subtree and elements to its right would consist of the right subtree. This can be solved recursively till no more elements would be left.

**Algorithm:**

- Consider the element at the middle of the array and make it the root of the tree.
- Now make a recursive function and for each half:
- Find the middle element of the left half and make it the root of the left child.
- Find the middle element of the right half and make it the root of the right child.

- Continue recursing for each half until all elements have been inserted in the tree.

**Implementation of the Approach:**

### C++ Code

TreeNode * sortedArrayToBST(vector < int > & nums) { int len = nums.size(); TreeNode * root = NULL; return helper(root, nums, 0, len - 1); } TreeNode * helper(TreeNode * root, vector < int > & nums, int l, int r) { if (l <= r) { int m = l + (r - l) / 2; root = new TreeNode(nums[m]); root -> left = helper(NULL, nums, l, m - 1); root -> right = helper(NULL, nums, m + 1, r); } return root; }

### Java Code

public TreeNode helper(int left, int right) { if (left > right) return null; int p = (left + right) / 2; TreeNode root = new TreeNode(nums[p]); root.left = helper(left, p - 1); root.right = helper(p + 1, right); return root; } public TreeNode sortedArrayToBST(int[] nums) { return helper(0, nums.length - 1); }

### Python Code

def sortedArrayToBST(nums): def helper(left, right): if left > right: return None p = (left + right) // 2 root = TreeNode(nums[p]) root.left = helper(left, p - 1) root.right = helper(p + 1, right) return root return helper(0, len(nums) - 1)

**Time Complexity:** O(N), where N is the total size of the array.

**Space Complexity:** O(h), where h is the height of the tree.

**Practice Questions:**

## FAQ

**What is the time and space complexity of the recursive approach?**The time and space complexity of the recursive approach is O(N) and O(h).

**What is a Binary Search Tree?**A**Binary Search Tree**is a binary tree that satisfies the following property:- The left node value is smaller than its parents.
- The right node value is greater than its parents.