LC108. Convert Sorted Array to Binary Search Tree

Problem Description

Source: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

For example: Given the sorted array: [-10, -3, 0, 5, 9], return the following tree:

        0
       / \
     -3   9
     /   /
   -10  5

Solution

High level strategy

To ensure that both sides of the tree has an equal amount of nodes, and to maintain the binary search tree invariant, we must always choose the middle element of the input array as our root node. After setting the root node of the tree, we split the input array in two sub-arrays to repeat the aforementioned logic. The left sub-array will start from the beginning of the array up to the index of the middle node. The right sub-arry will start from the index after the middle node, up to the end of the array. The middle element of every sub-array will always be the root node of every subtree.

For example:

Input: [1, 2, 3, 4, 5, 6, 7, 8, 9];
Output:             [5] ---> root: [5], left: [1, 2, 3, 4], right: [6, 7, 8, 9];
                  /     \
               [3]       [7] ---> root: [3], left: [1, 2], right: [4]; 
              /   \     /   \     root: [7], left: [6], right: [8, 9];
            [1]   [4] [6]   [8] ---> root: [1], left: null, right[2];
              \               \      root: [8], left: null, right[9];
              [2]             [9]

The time and space complexity of this solution are both O(n), where 'n' is equal to the number of nodes.

Code

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 **/

const sortedArrayToBST = (nums) => {

    let helper = (left, right) => {
        if (left > right) return null;

        let index = Math.floor((left + right) / 2);
        let root = new TreeNode(nums[index]);
        root.left = helper(left, index - 1);
        root.right = helpter(index + 1, right);

        return root;
    };

    return helper(0, nums.length - 1);
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public TreeNode sortedArrayToBST(int[] nums) {
  int len = nums.length;
  if (len == 0) return null;
  if (len == 1) {
      TreeNode root = new TreeNode(nums[0]);
      return root;
  }
  int medianIdx = len % 2 == 0 ? len / 2 - 1 : len / 2;
  TreeNode root = new TreeNode(nums[medianIdx]);
  root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, medianIdx));
  root.right = sortedArrayToBST(Arrays.copyOfRange(nums, medianIdx + 1, len));
  return root;
}