Convert Sorted Array to Binary Search Tree

Problem

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

Solution

Two Pointers Solution

public class Solution {
/**
 * 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) {
        if (nums == null || nums.length == 0) return null;
        return helper(nums, 0, nums.length - 1);
    }

    private TreeNode helper(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, left, mid - 1);
        node.right = helper(nums, mid + 1, right);
        return node;
    }
}

Analysis

This is a typical problem and a general ability for programmers
The key idea is to use two pointer and recursive method to help construct the BST
We init the root node and then set its left and right subtree with corresponding indices
Because of recursive calls on the method, we will have a BST at the end

Complexity

• Time: O(n), we visit each node once
• Space: O(n), the recursive method will be called n times