Leetcode: Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.


Understand the problem:
As described in the problem, given an array sorted in ascending order, convert it to a balanced BST.

You must understand what is the height balanced BST. For this problem, 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.

Solution:
One idea is for a BST, the left children must be less than the parent, while the right children are greater than the parent. So following this idea, we could partition the array into two parts evenly. The middle point must be the parent, and the left part is less than the parent and must be the left children. The right part is greater than the middle and must be the right children. As a result, we divide the problem into two smaller sub-problems. We can recursively repeat this process until there is only one node for the left or right child. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0) return null;
        
        return toBST(num, 0, num.length - 1);
    }
    
    private TreeNode toBST(int[] num, int lo, int hi) {
        if (lo > hi) return null;
        
        int mid = (lo + hi)/2;
        
        TreeNode root = new TreeNode(num[mid]);
        root.left = toBST(num, lo, mid - 1);
        root.right = toBST(num, mid + 1, hi);
        
        return root;
    }
}

Summary:
The problem is relatively straight-forward. The key idea is partition. Also, it is not hard to find that the idea is very similar to binary search. So we can see that it is very important to understand the basic data structure and algorithms.