108. Convert Sorted Array to Binary Search Tree

Description

Given an array where elements are sorted in ascending order, convert it to a 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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [-10, -3, 0, 5, 9]

Output: [0, -10, 5, null, -3, null, 9]

One possible answer is: [0, -10, 5, null, -3, null, 9], which represents the following height balanced BST:

Solutions

TreeNode

// 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;
    }
}

Solution 1

/**
 * Time complexity : O(N) since we visit each node exactly once.
 * Space complexity : O(N) to keep the output, and O(logN) for the 
 *    recursion stack.
 */

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        return sortedArrayToBST(nums, 0, nums.length-1);
    }
    
    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if(start > end) return null;
        
        int index = (start + end)/2;
        
        TreeNode node = new TreeNode(nums[index]);
        node.left = sortedArrayToBST(nums, start, index-1);
        node.right = sortedArrayToBST(nums, index+1, end);
        
        return node;
    }
}

Follow up

• Sorted Linked List to Balanced BST - GFG