Sorted Array to Balanced BST

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.

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:

Sorted Array To Balanced BST

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:
  1. The left node value is smaller than its parents.
  2. The right node value is greater than its parents.