0108. Convert Sorted Array to Binary Search Tree

Easy | Binary Search Tree + Inorder Traversal | 40 ms (98.49%), 16.1 MB (78.29%)

❓ Problem Statement

Source: LeetCode - Convert Sorted Array to Binary Search Tree GitHub: Solution / Performance

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

✍🏻 Constraints & Example

Constraints:

• 1 <= nums.length <= 10^4

• -10^4 <= nums[i] <= 10^4

• nums is sorted in a strictly increasing order.

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.

💡 Ideas

Inorder traversal of BST is an array sorted in ascending order.

Based on the above understanding, the middle element in an array sorted in ascending order is the root of BST. Therefore, we can create a helper function to retrieve the middle element and recursively call itself to find the middle element in the left and right parts by boundary indexes (start and end).

Note that the termination of recursion is important.

• If start > end, there are no elements for the subtree. Return None.

• if start == end, there is only one element for the subtree. Return TreeNode.

🤖 Python3

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        #: (base case)
        if len(nums) == 1: return TreeNode(nums[0])
        if len(nums) == 2: return TreeNode(nums[0], None, TreeNode(nums[1]))
        
        # ==================================================
        #  Binary Search Tree + Inorder Traversal          =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        self.nums = nums
        return self.subTree(0, len(nums) - 1)
        
    def subTree(self, start: int, end: int) -> TreeNode:
        if start  > end: return None
        if start == end: return TreeNode(self.nums[start])
        
        mid = (start + end) // 2
        
        node = TreeNode(self.nums[mid])
        node.left  = self.subTree(start, mid - 1)
        node.right = self.subTree(mid + 1, end)
        
        return node

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    int[] nums;
    
    public TreeNode subTree(int start, int end) {
        if(start  > end) return null;
        if(start == end) return new TreeNode(nums[start]);
            
        int center = (start + end) / 2;
        
        TreeNode node = new TreeNode(nums[center]);
        node.left  = subTree(start, center - 1);
        node.right = subTree(center + 1, end);
        
        return node;
    }
    
    public TreeNode sortedArrayToBST(int[] nums) {
        /* base case */
        if(nums.length == 1) return new TreeNode(nums[0]);
        
        this.nums = nums;
        
        return subTree(0, nums.length - 1);
    }
}