108. Convert Sorted Array to Binary Search Tree

Published on August 3, 2023

Question

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced* binary search tree*.

Algorithm

To create a height balanced tree we just create the tree level by level.

To ensure it's a BST, we need to select the middle element since the original numbers are sorted. The middle element is the root ( the binary search tree in-order traversal).

We solve this question using recursive way. For the middle element in the array, we make it root, and the left child is we select middle element from the left part or the array, and same to the right side.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length-1);
    }
    
    private TreeNode helper(int[] nums, int start, int end) {
        if (start > end) return null;
        int mid = nums[start + (end - start)/2];
        TreeNode root = new TreeNode(mid);
        root.left = helper(nums, start, start + (end-start) / 2 - 1);
        root.right = helper(nums, start + (end-start)/2 + 1, end);
        return root;
    }
}