Jobs

Interviews

Discussions

Convert Sorted Array to Binary Search Tree

Easy

Asked by:

More companies

148 views

Topics:

TreesRecursionArrays

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

Example 1:

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:

Example 2:

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

Constraints:

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

Try coding it in LeetCode

Convert Sorted Array to Binary Search Tree

Easy

Asked by:

148 views

Topics:

TreesRecursionArrays

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

Example 1:

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:

Example 2:

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

Constraints:

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

Try coding it in LeetCode

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 should be the return value if the input array `nums` is empty?
The problem states the input array is sorted. Can we assume it contains distinct integers, or could there be duplicates?
Given that a height-balanced BST can be constructed in multiple ways from a sorted array, is any valid height-balanced BST acceptable, or is there a preferred structure, like always picking the middle element as the root?
What are the constraints on the size of the input array and the range of values for the integers within it?
Just to confirm the definition of 'height-balanced' – does this mean the heights of the left and right subtrees of any node can differ by at most 1, consistent with an AVL tree property?

Brute Force Solution

Approach

The brute force strategy involves trying every single number from the sorted list as the starting point, or the top, of our tree. For each choice, we then explore all the possible ways to arrange the remaining numbers to see if we can build a valid and balanced family tree of numbers.

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

First, pick any number from the sorted list to be the main ancestor, or the root, of the tree.
Once you've picked the root, all the smaller numbers from the original list must go on its left side, and all the larger numbers must go on its right side.
Now, look at the group of smaller numbers. From this group, pick any number to be the root of the left-side family.
Similarly, from the group of larger numbers, pick any number to be the root of the right-side family.
Continue this process of picking a root for each smaller subgroup of numbers and splitting the rest until every number from the original list has been placed in the tree.
After building a complete tree, check if it's 'balanced', meaning the left and right sides of every number have roughly the same number of descendants.
If it's not a valid or balanced tree, discard it and go back to try a different arrangement by picking a different number as a root at some step.
Repeat this entire process for every possible initial number you could have picked as the main root, and for every possible sub-root choice along the way, until you find one of the arrangements that results in a balanced tree.

Code Implementation

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

def sortedArrayToBST(nums):
    import itertools

    def get_height(node):
        if not node:
            return 0
        return 1 + max(get_height(node.left), get_height(node.right))

    def is_balanced(root):
        if not root:
            return True
        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 build_all_trees(available_numbers):
        if not available_numbers:
            yield None
            return

        # This loop tries every number in the current list as the root for this subtree.
        for index, potential_root_value in enumerate(available_numbers):
            left_side_numbers = available_numbers[:index]
            right_side_numbers = available_numbers[index+1:]
            
            # Recursively generate all possible left and right subtrees from the remaining numbers.
            for left_subtree in build_all_trees(left_side_numbers):
                for right_subtree in build_all_trees(right_side_numbers):
                    current_root = TreeNode(potential_root_value)
                    current_root.left = left_subtree
                    current_root.right = right_subtree
                    yield current_root

    # Iterate through all permutations of the input numbers, as the root can be any element.
    for number_permutation in itertools.permutations(nums):
        generated_trees = list(build_all_trees(list(number_permutation)))
        
        for potential_tree_root in generated_trees:
            # After building a tree, we must check its height balance property for validity.
            if is_balanced(potential_tree_root):
                return potential_tree_root

    return None

Big(O) Analysis

Time Complexity

O(n!) – The described brute-force approach explores every possible permutation of the input numbers to form a tree structure. For an input of size n, there are n choices for the root, (n-1) choices for the next node, and so on, leading to n factorial (n!) permutations. For each permutation, we would need to construct the tree and then validate its height-balanced property, which is a very expensive operation. The dominant factor is the sheer number of trees to check, which grows factorially with the input size n, making this approach extremely inefficient.

Space Complexity

O(N) – The algorithm builds a complete tree before checking its validity, requiring space to store all N nodes. Additionally, the process of trying every possible arrangement involves recursion. In the worst-case scenario, where the algorithm tries a skewed tree structure (like picking the smallest element as the root repeatedly), the recursive call stack can reach a depth of N, contributing to the overall space complexity.

Optimal Solution

Approach

To build a balanced tree from a sorted list of numbers, we should pick the middle number as the top of the tree. This single choice naturally splits the remaining numbers into two equal-sized groups, which we can then use to build the left and right sides of the tree in the same way.

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

Start with the entire sorted list of numbers.
Find the exact middle number in the current list and make it a new node in our tree. This will be the top of the current section.
This choice splits the list into two smaller groups: all the numbers to its left and all the numbers to its right.
Take the group of numbers to the left of the middle one and repeat the whole process on it. The resulting smaller tree will become the left branch of the node we just created.
Similarly, take the group of numbers to the right of the middle one and do the same thing. This will form the right branch.
Continue this process of picking the middle, splitting the list, and building smaller trees until you run out of numbers to place.
Because we always pick the middle element, the tree naturally becomes balanced, with roughly the same number of nodes on the left and right sides at every level.

Code Implementation

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

def sortedArrayToBST(nums):
    def build_tree_from_range(left_index, right_index):
        # The base case: if the range is empty, there are no more numbers to place.
        if left_index > right_index:

            return None

        # Picking the middle element ensures the tree remains height-balanced.
        middle_index = (left_index + right_index) // 2

        root_node = TreeNode(nums[middle_index])

        # Recursively build the left subtree from the left half of the current range.
        root_node.left = build_tree_from_range(left_index, middle_index - 1)

        # Recursively build the right subtree from the right half of the current range.
        root_node.right = build_tree_from_range(middle_index + 1, right_index)

        return root_node

    return build_tree_from_range(0, len(nums) - 1)

Big(O) Analysis

Time Complexity

O(n) – The algorithm processes each number from the input array exactly once to create a corresponding node in the binary search tree. The core operation is finding the middle of a subarray and creating a node, which is a constant time action when using indices. Since this constant time work is performed for each of the n elements in the input array, the total number of operations is directly proportional to n. This linear relationship means the time complexity simplifies to O(n).

Space Complexity

O(log N) – The algorithm follows a recursive approach, as described by repeating the process on the left and right groups of numbers. This recursion creates a call stack, and since we always pick the middle element, the tree is balanced. The maximum depth of this balanced tree, and therefore the maximum depth of the recursion stack, is proportional to the logarithm of the number of elements, N. Thus, the auxiliary space used by the call stack is O(log N).

Edge Cases

Case	How to Handle
Input array is empty	The recursive base case should handle this by returning null, representing an empty tree.
Input array has only one element	A single node is created and returned, which is by definition a valid height-balanced BST.
Input array has an even number of elements	Choosing either of the two middle elements as the root will produce a valid, though different, height-balanced BST.
Input array contains duplicate values	The standard recursive algorithm handles duplicates correctly, placing them in the tree according to BST rules.
Input array contains negative numbers and zero	The algorithm is agnostic to the sign of the numbers and will correctly construct the BST as long as the array is sorted.
Input array is very large, potentially causing a stack overflow	A deeply recursive approach might fail; an iterative solution using a stack can be used to avoid this.
Multiple valid height-balanced BSTs are possible	The problem allows for any valid height-balanced BST, so a consistent choice for the root (e.g., always the middle-left element) is sufficient.
Input array contains integer boundary values (e.g., INT_MIN, INT_MAX)	The values themselves do not affect the tree construction logic, so the standard algorithm works without modification.

Input array is empty

How to Handle:

The recursive base case should handle this by returning null, representing an empty tree.

Input array has only one element

How to Handle:

A single node is created and returned, which is by definition a valid height-balanced BST.

Input array has an even number of elements

How to Handle:

Choosing either of the two middle elements as the root will produce a valid, though different, height-balanced BST.

Input array contains duplicate values

How to Handle:

The standard recursive algorithm handles duplicates correctly, placing them in the tree according to BST rules.

Input array contains negative numbers and zero

How to Handle:

The algorithm is agnostic to the sign of the numbers and will correctly construct the BST as long as the array is sorted.

Input array is very large, potentially causing a stack overflow

How to Handle:

A deeply recursive approach might fail; an iterative solution using a stack can be used to avoid this.

Multiple valid height-balanced BSTs are possible

How to Handle:

The problem allows for any valid height-balanced BST, so a consistent choice for the root (e.g., always the middle-left element) is sufficient.

Input array contains integer boundary values (e.g., INT_MIN, INT_MAX)

How to Handle:

The values themselves do not affect the tree construction logic, so the standard algorithm works without modification.

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 should be the return value if the input array `nums` is empty?
The problem states the input array is sorted. Can we assume it contains distinct integers, or could there be duplicates?
Given that a height-balanced BST can be constructed in multiple ways from a sorted array, is any valid height-balanced BST acceptable, or is there a preferred structure, like always picking the middle element as the root?
What are the constraints on the size of the input array and the range of values for the integers within it?
Just to confirm the definition of 'height-balanced' – does this mean the heights of the left and right subtrees of any node can differ by at most 1, consistent with an AVL tree property?

Brute Force Solution

Approach

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

First, pick any number from the sorted list to be the main ancestor, or the root, of the tree.
Once you've picked the root, all the smaller numbers from the original list must go on its left side, and all the larger numbers must go on its right side.
Now, look at the group of smaller numbers. From this group, pick any number to be the root of the left-side family.
Similarly, from the group of larger numbers, pick any number to be the root of the right-side family.
Continue this process of picking a root for each smaller subgroup of numbers and splitting the rest until every number from the original list has been placed in the tree.
After building a complete tree, check if it's 'balanced', meaning the left and right sides of every number have roughly the same number of descendants.
If it's not a valid or balanced tree, discard it and go back to try a different arrangement by picking a different number as a root at some step.
Repeat this entire process for every possible initial number you could have picked as the main root, and for every possible sub-root choice along the way, until you find one of the arrangements that results in a balanced tree.

Code Implementation

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

def sortedArrayToBST(nums):
    import itertools

    def get_height(node):
        if not node:
            return 0
        return 1 + max(get_height(node.left), get_height(node.right))

    def is_balanced(root):
        if not root:
            return True
        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 build_all_trees(available_numbers):
        if not available_numbers:
            yield None
            return

        # This loop tries every number in the current list as the root for this subtree.
        for index, potential_root_value in enumerate(available_numbers):
            left_side_numbers = available_numbers[:index]
            right_side_numbers = available_numbers[index+1:]
            
            # Recursively generate all possible left and right subtrees from the remaining numbers.
            for left_subtree in build_all_trees(left_side_numbers):
                for right_subtree in build_all_trees(right_side_numbers):
                    current_root = TreeNode(potential_root_value)
                    current_root.left = left_subtree
                    current_root.right = right_subtree
                    yield current_root

    # Iterate through all permutations of the input numbers, as the root can be any element.
    for number_permutation in itertools.permutations(nums):
        generated_trees = list(build_all_trees(list(number_permutation)))
        
        for potential_tree_root in generated_trees:
            # After building a tree, we must check its height balance property for validity.
            if is_balanced(potential_tree_root):
                return potential_tree_root

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with the entire sorted list of numbers.
Find the exact middle number in the current list and make it a new node in our tree. This will be the top of the current section.
This choice splits the list into two smaller groups: all the numbers to its left and all the numbers to its right.
Take the group of numbers to the left of the middle one and repeat the whole process on it. The resulting smaller tree will become the left branch of the node we just created.
Similarly, take the group of numbers to the right of the middle one and do the same thing. This will form the right branch.
Continue this process of picking the middle, splitting the list, and building smaller trees until you run out of numbers to place.
Because we always pick the middle element, the tree naturally becomes balanced, with roughly the same number of nodes on the left and right sides at every level.

Code Implementation

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

def sortedArrayToBST(nums):
    def build_tree_from_range(left_index, right_index):
        # The base case: if the range is empty, there are no more numbers to place.
        if left_index > right_index:

            return None

        # Picking the middle element ensures the tree remains height-balanced.
        middle_index = (left_index + right_index) // 2

        root_node = TreeNode(nums[middle_index])

        # Recursively build the left subtree from the left half of the current range.
        root_node.left = build_tree_from_range(left_index, middle_index - 1)

        # Recursively build the right subtree from the right half of the current range.
        root_node.right = build_tree_from_range(middle_index + 1, right_index)

        return root_node

    return build_tree_from_range(0, len(nums) - 1)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array is empty	The recursive base case should handle this by returning null, representing an empty tree.
Input array has only one element	A single node is created and returned, which is by definition a valid height-balanced BST.
Input array has an even number of elements	Choosing either of the two middle elements as the root will produce a valid, though different, height-balanced BST.
Input array contains duplicate values	The standard recursive algorithm handles duplicates correctly, placing them in the tree according to BST rules.
Input array contains negative numbers and zero	The algorithm is agnostic to the sign of the numbers and will correctly construct the BST as long as the array is sorted.
Input array is very large, potentially causing a stack overflow	A deeply recursive approach might fail; an iterative solution using a stack can be used to avoid this.
Multiple valid height-balanced BSTs are possible	The problem allows for any valid height-balanced BST, so a consistent choice for the root (e.g., always the middle-left element) is sufficient.
Input array contains integer boundary values (e.g., INT_MIN, INT_MAX)	The values themselves do not affect the tree construction logic, so the standard algorithm works without modification.

Input array is empty

How to Handle:

The recursive base case should handle this by returning null, representing an empty tree.

Input array has only one element

How to Handle:

A single node is created and returned, which is by definition a valid height-balanced BST.

Input array has an even number of elements

How to Handle:

Choosing either of the two middle elements as the root will produce a valid, though different, height-balanced BST.

Input array contains duplicate values

How to Handle:

The standard recursive algorithm handles duplicates correctly, placing them in the tree according to BST rules.

Input array contains negative numbers and zero

How to Handle:

The algorithm is agnostic to the sign of the numbers and will correctly construct the BST as long as the array is sorted.

Input array is very large, potentially causing a stack overflow

How to Handle:

A deeply recursive approach might fail; an iterative solution using a stack can be used to avoid this.

Multiple valid height-balanced BSTs are possible

How to Handle:

The problem allows for any valid height-balanced BST, so a consistent choice for the root (e.g., always the middle-left element) is sufficient.

Input array contains integer boundary values (e.g., INT_MIN, INT_MAX)

How to Handle:

The values themselves do not affect the tree construction logic, so the standard algorithm works without modification.