SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to convert a sorted array into a height-balanced binary search tree (BST). A height-balanced BST is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Given an array where elements are sorted in ascending order, we need to construct a BST with minimal height.

For example, given the sorted array [-10, -3, 0, 5, 9], one possible height-balanced BST is:

Intuition

A height-balanced BST can be constructed by recursively choosing the middle element of the array (or subarray) as the root node, and then applying the same logic to the left and right halves of the array to create the left and right subtrees.

By always picking the middle element, we ensure that the tree remains balanced, as the number of nodes in the left and right subtrees will differ by at most one.

Approach

1. Base Case:

   • If the start index is greater than the end index, return None (no node to create).

2. Recursive Case:

   • Find the middle index of the current subarray.
   • Create a new TreeNode with the value of the middle element.
   • Recursively build the left subtree using the left half of the current subarray.
   • Recursively build the right subtree using the right half of the current subarray.
   • Return the root node.

3. Main Function:

   • Call the helper function with the initial indices 0 and len(nums) - 1 to cover the entire array.
   • Return the root of the constructed BST.

#Complexity

Time Complexity:

• O(n)

Each element in the array is visited exactly once to create a node, resulting in a linear time complexity where n is the number of elements in the array. Space Complexity: O(log n)

space complexity:

Is determined by the recursion stack. Since the tree is balanced, the maximum depth of the recursion is log n. Additional space for the BST nodes is O(n), but since this space is for the output rather than auxiliary, it's not counted in the space complexity analysis.

Code

C++

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

private:
    TreeNode* helper(vector<int>& nums, int start, int end) {
        if (start > end) {
            return nullptr;
        }
        
        int mid = start + (end - start) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, start, mid - 1);
        root->right = helper(nums, mid + 1, end);
        
        return root;
    }
};

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        return self.helper(nums, 0, len(nums) - 1)
    
    def helper(self, nums: List[int], start: int, end: int) -> Optional[TreeNode]:
        if start > end:
            return None
        
        mid = (start + end) // 2
        root = TreeNode(nums[mid])
        root.left = self.helper(nums, start, mid - 1)
        root.right = self.helper(nums, mid + 1, end)
        
        return root

Java

class Solution {
    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 start, int end) {
        if (start > end) {
            return null;
        }
        
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, start, mid - 1);
        root.right = helper(nums, mid + 1, end);
        
        return root;
    }
}

JavaScript

var sortedArrayToBST = function (nums) 

{
    const helper = (start, end) => {
        if (start > end) {
            return null;
        }
        const mid = Math.floor((start + end) / 2);
        const root = new TreeNode(nums[mid]);
        root.left = helper(start, mid - 1);
        root.right = helper(mid + 1, end);
        return root;
    };

    return helper(0, nums.length - 1);
};