Convert Sorted Array to Binary Search Tree

Easy

Google

1 view

Topics:

TreesRecursion

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

Here's a breakdown of the requirements:

Sorted Input: The input array nums is guaranteed to be sorted in ascending order.
Height-Balanced BST: The resulting binary search tree must be height-balanced, meaning the height difference between the left and right subtrees of any node is no more than 1.

For example:

Input: nums = [-10, -3, 0, 5, 9]
Possible Output: [0, -3, 9, -10, null, 5] (This represents a valid height-balanced BST. Another valid output is [0, -10, 5, null, -3, null, 9])

Another example:

Input: nums = [1, 3]
Possible Output: [3, 1] (or [1, null, 3])

Constraints:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in a strictly increasing order.

How would you approach this problem and implement an efficient solution? Explain your reasoning and the time and space complexity of your solution.

Convert Sorted Array to Binary Search Tree

Easy

Google

1 view

Topics:

TreesRecursion

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

Here's a breakdown of the requirements:

Sorted Input: The input array nums is guaranteed to be sorted in ascending order.
Height-Balanced BST: The resulting binary search tree must be height-balanced, meaning the height difference between the left and right subtrees of any node is no more than 1.

For example:

Input: nums = [-10, -3, 0, 5, 9]
Possible Output: [0, -3, 9, -10, null, 5] (This represents a valid height-balanced BST. Another valid output is [0, -10, 5, null, -3, null, 9])

Another example:

Input: nums = [1, 3]
Possible Output: [3, 1] (or [1, null, 3])

Constraints:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in a strictly increasing order.

How would you approach this problem and implement an efficient solution? Explain your reasoning and the time and space complexity of your solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the input array is empty?
Can the input array contain negative numbers?
By 'height-balanced,' do you mean strictly AVL balanced or is a looser definition of balance acceptable (e.g., difference in height between subtrees is no more than 1)?
Is it acceptable to modify the input array during the construction of the BST?
Are the integers in the input array guaranteed to be unique and sorted in ascending order, as stated?

Brute Force Solution

Approach

The goal is to make a perfectly balanced tree from an ordered list. The brute force way is to try every single possible tree shape you can make with the numbers given.

Here's how the algorithm would work step-by-step:

Consider every possible number in the list as the very top of the tree.
For each of those choices, try every possible way to split the remaining numbers into a left subtree and a right subtree.
For each of those subtrees, repeat the process: try every number within those subtrees as the top of those smaller trees.
Keep going, splitting and building smaller and smaller trees, until you've used every number in the original list.
Check each of these tree structures to see if it meets the requirements of a binary search tree (smaller numbers on the left, bigger numbers on the right) and if it's perfectly balanced.
If you find a tree that meets both requirements, you have found the solution.

Code Implementation

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

def is_binary_search_tree(root, min_value=float('-inf'), max_value=float('inf')):
    if root is None:
        return True

    if root.value <= min_value or root.value >= max_value:
        return False

    return (is_binary_search_tree(root.left, min_value, root.value) and\
            is_binary_search_tree(root.right, root.value, max_value))

def is_balanced(root):
    if root is None:
        return True
    
    def get_height(node):
        if node is None:
            return 0
        return 1 + max(get_height(node.left), get_height(node.right))
    
    left_height = get_height(root.left)
    right_height = get_height(root.right)
    
    if abs(left_height - right_height) > 1:
        return False
    
    return is_balanced(root.left) and is_balanced(root.right)

def convert_sorted_array_to_binary_search_tree_brute_force(sorted_array):
    best_tree = None

    def generate_trees(numbers):
        if not numbers:
            return [None]

        trees = []
        for index in range(len(numbers)):
            # Consider each number as the root.
            root_value = numbers[index]

            left_sub_array = numbers[:index]
            right_sub_array = numbers[index+1:]

            left_subtrees = generate_trees(left_sub_array)
            right_subtrees = generate_trees(right_sub_array)

            # Try every combination of subtrees
            for left_subtree in left_subtrees:
                for right_subtree in right_subtrees:
                    root = TreeNode(root_value)
                    root.left = left_subtree
                    root.right = right_subtree
                    trees.append(root)
        return trees
    
    all_possible_trees = generate_trees(sorted_array)

    #Iterate and evaluate whether a tree fits the given criteria
    for possible_tree in all_possible_trees:
        if is_binary_search_tree(possible_tree) and is_balanced(possible_tree):
            best_tree = possible_tree
            return best_tree

    return None

Big(O) Analysis

Time Complexity

O(2^n * n) – The algorithm explores every possible binary tree structure that can be formed from the sorted array. For an array of size n, there are an exponential number of possible tree structures, approximately 2^n. For each of these tree structures, we need to validate if it is a valid Binary Search Tree, which would take O(n) time in the worst case by traversing the entire tree. Therefore the overall time complexity would be O(2^n * n).

Space Complexity

O(N^2) – The brute force approach described recursively explores all possible tree structures. The recursion depth could potentially reach N (the number of elements in the input array). At each level of recursion, we're effectively splitting the remaining array and creating subproblems which might require temporary storage on the order of N in the worst case. Furthermore, each tree is validated, requiring space to hold tree node information. This repeated tree construction and splitting, combined with the recursive calls, results in auxiliary space usage approximated by O(N^2) in the worst case because a perfectly unbalanced tree would require storing information at almost every node during validation.

Optimal Solution

Approach

The core idea is to build the tree from the middle outward. This ensures that the tree stays balanced, which leads to optimal performance. By always picking the middle as the root we guarantee we are building the most balanced structure possible at each step.

Here's how the algorithm would work step-by-step:

Find the middle value of the sorted set of numbers.
Make this middle value the very top, or root, of our tree.
Now, split the numbers into two groups: those smaller than the middle, and those larger than the middle.
Use the smaller group of numbers to build the left side of the tree, and the larger group to build the right side of the tree. Do this the same way: find the middle, make it a node, split again.
Keep repeating the process of finding the middle and splitting until there are no numbers left in the groups.
Because we always start with the middle, we get a tree that's balanced from top to bottom, which keeps things efficient.

Code Implementation

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

def sortedArrayToBST(nums):
    def construct_bst(left_index, right_index):
        if left_index > right_index:
            return None

        # Find the middle index to ensure balanced tree structure
        middle_index = (left_index + right_index) // 2

        root_node = TreeNode(nums[middle_index])

        # Recursively build the left subtree
        root_node.left = construct_bst(left_index, middle_index - 1)

        # Recursively build the right subtree
        root_node.right = construct_bst(middle_index + 1, right_index)

        return root_node

    # Start with the entire array
    return construct_bst(0, len(nums) - 1)

Big(O) Analysis

Time Complexity

O(n) – The algorithm processes each of the n elements of the sorted array exactly once to create a node in the binary search tree. The recursive calls effectively divide the array into subarrays, ensuring each element is visited and added to the tree structure. Therefore, the time complexity is directly proportional to the number of elements, resulting in a linear time complexity of O(n).

Space Complexity

O(log N) – The algorithm uses recursion to build the binary search tree. In the worst-case scenario (a skewed tree), the depth of the recursion can be N. However, because the input array is repeatedly split in half, leading to balanced tree construction as intended, the maximum depth of the recursion will be log N. Each recursive call consumes stack space, and therefore the space complexity is determined by the maximum depth of the recursive call stack, which is O(log N), where N is the number of elements in the input array.

Edge Cases

Case	How to Handle
Empty input array	Return null or None, indicating an empty tree.
Array with a single element	Create a root node with the single element and return it.
Array with two elements	Choose either element as root and the other as its left or right child, maintaining BST property.
Large array (stress test)	The algorithm should have logarithmic height, preventing stack overflow with recursion and scaling efficiently.
Array with all negative numbers	The algorithm should handle negative numbers correctly due to the sorted nature of the input.
Array with extremely large or small numbers (integer overflow)	The code should be written to avoid integer overflow during calculations of the middle index, potentially using long types.
Input array containing zero	Zero should be handled like any other integer according to its sorted position.
Array close to maximum integer size	Midpoint calculation should not cause overflow, which can be avoided by using start + (end - start) / 2.