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

Examples

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

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

/**
 * 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

Previous107. Binary Tree Level Order Traversal II Next109. Convert Sorted List to Binary Search Tree

Last updated 5 years ago

Was this helpful?