Convert Sorted Array to Binary Search Tree

Creating a height-balanced binary search tree (BST) from a sorted array can be done using a recursive approach. Since the array is sorted, the middle element can be the root of the tree, and the elements to the left and right of the middle can form the left and right subtrees, respectively.

Here’s the process:

  1. Find the Middle: Determine the middle element of the array.
  2. Create the Root: Create a node using the middle element as the root of the current subtree.
  3. Recursive Left and Right Calls: Recursively apply the process to the left and right halves of the array to create the left and right subtrees.
  4. Base Case: If the array is empty, return None.

Here’s a code implementation of this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None

        mid = len(nums) // 2
        root = TreeNode(val=nums[mid])

        root.left = self.sortedArrayToBST(nums[:mid])  # Left subtree
        root.right = self.sortedArrayToBST(nums[mid+1:])  # Right subtree

        return root

Key Insights:

  • Since the array is sorted, the middle element ensures that the binary search property is maintained.
  • The recursive approach naturally ensures that the resulting tree is height-balanced, as the array is split into roughly equal halves at each step.
  • The time complexity of this solution is ( O(n) ), where ( n ) is the number of elements in the input array. The space complexity is ( O(\log n) ) due to the recursion stack, assuming a balanced tree.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} nums
# @return {TreeNode}
def wrapper(nums, low, high)
  if low > high
    return
  end
  
  mid = (low + high)/2
  root = TreeNode.new(nums[mid])
  
  root.left = wrapper(nums, low, mid - 1)
  root.right = wrapper(nums, mid + 1, high)  
  
  return root
end

def sorted_array_to_bst(nums)
  wrapper(nums, 0, nums.size-1)
end

Identifying Problem Isomorphism

“Convert Sorted Array to Binary Search Tree” deals with constructing a height-balanced binary search tree from a sorted array.

A problem that has a similar structure is “109. Convert Sorted List to Binary Search Tree”. In this problem, you are given a singly linked list where elements are sorted in ascending order, and you are to convert it to a height balanced BST.

The reasoning is that both problems involve a transformation from a sorted linear data structure to a binary search tree while ensuring that the resultant tree is height balanced.

The difference between these problems is in the input data structure: one deals with an array and the other with a singly linked list. Therefore, the mapping is an approximate isomorphism, as the overall concept and structure of the problems are similar, but the exact details and implementation would differ based on the input data structure.

“108. Convert Sorted Array to Binary Search Tree” involves creating a height-balanced binary search tree (BST) from a sorted array.

A similar problem is “109. Convert Sorted List to Binary Search Tree”. This problem also involves constructing a height-balanced BST, but this time from a sorted linked list instead of a sorted array.

Both problems involve the concept of constructing a balanced BST from sorted data. Even though the type of data structure containing the sorted data differs (array vs. linked list), the principle and methods used to solve these problems are the same: to ensure balance, we would select the middle element to be the root and apply the same logic recursively to the left and right parts. Therefore, “109. Convert Sorted List to Binary Search Tree” is an approximate isomorphic problem to “108. Convert Sorted Array to Binary Search Tree”.

10 Prerequisite LeetCode Problems

“Convert Sorted Array to Binary Search Tree” involves arrays, binary search, and binary trees. Here are some simpler problems in preparation for this problem:

  1. 108. Convert Sorted List to Binary Search Tree: This problem is very similar but instead of an array, you are given a sorted linked list.

  2. 104. Maximum Depth of Binary Tree: This will help you get comfortable with tree traversals.

  3. 110. Balanced Binary Tree: Understanding what makes a tree balanced is crucial for this problem.

  4. 700. Search in a Binary Search Tree: This problem helps understand the property of Binary Search Trees.

  5. 101. Symmetric Tree: Helps in understanding tree structure and properties.

  6. 88. Merge Sorted Array: This problem involves manipulating sorted arrays.

  7. 153. Find Minimum in Rotated Sorted Array: This problem will give you practice with binary search in an array.

  8. 167. Two Sum II - Input array is sorted: This problem gives practice with sorted arrays.

  9. 278. First Bad Version: Another good problem for binary search practice.

  10. 35. Search Insert Position: This is a basic problem to understand binary search in sorted array.

These cover how to handle arrays, binary trees, and binary search, which are key concepts for solving the problem of converting a sorted array to a binary search tree.

1
2
3
4
5
6
7
8
9

    def recursive(self, nums):
        def rec(nums, start, end):
            if start <= end:
                mid = (start + end) // 2
                node = TreeNode(nums[mid])
                node.left = rec(nums, start, mid - 1)
                node.right = rec(nums, mid + 1, end)
                return node
        return rec(nums, 0, len(nums) - 1)

Problem Classification

This problem can be classified as follows:

  1. Binary Search Trees: The problem involves constructing a binary search tree. A binary search tree (BST) is a type of binary tree where the nodes are ordered in a specific way. Each node can have up to two successors, which are referred to as the left child and the right child.

  2. Recursion: The problem solution relies on the method of recursion, a process in which a function calls itself as a subroutine. This allows the function to be repeated several times, as it can call itself during its execution.

  3. Sorted Arrays: The input for this problem is a sorted array. Understanding properties of sorted arrays, particularly how they can be used to construct other data structures, is necessary for this problem.

  4. Balanced Trees: The problem specifically mentions constructing a binary search tree that is “height-balanced”. In this context, 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.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

Can you help me with finding the isomorphism for this problem?

Which problem does this problem map to the corresponding isomorphic problem on Leetcode ?

Language Agnostic Coding Drills

  1. Understanding Binary Trees: The problem involves creating a binary search tree from a sorted list. This requires a basic understanding of the structure and properties of binary trees and specifically, binary search trees.

  2. Recursive Functions: This problem involves writing a recursive function. Understanding recursion, the base case and the recursive case is key to this problem.

  3. Understanding Binary Search: The implementation uses a binary search technique to find the middle element and uses that as a root node. Binary search is a key concept to understand here.

Targeted Drills in Python

  1. Understanding Binary Trees:
1
2
3
4
5

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
  1. Recursive Functions:
1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # prints 120
  1. Understanding Binary Search:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def binary_search(arr, x):
    start = 0
    end = len(arr) - 1
    mid = 0

    while start <= end:
        mid = (end + start) // 2

        if arr[mid] < x:
            start = mid + 1
        elif arr[mid] > x:
            end = mid - 1
        else:
            return mid
    return -1

Problem-Specific Drill:

Now let’s combine all of these concepts into a drill specific to the problem at hand:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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

class Solution:
    def sortedArrayToBST(self, nums):
        def rec(nums, start, end):
            if start <= end:
                mid = (start + end) // 2
                node = TreeNode(nums[mid])
                node.left = rec(nums, start, mid - 1)
                node.right = rec(nums, mid + 1, end)
                return node
        return rec(nums, 0, len(nums) - 1)

solution = Solution()
print(solution.sortedArrayToBST([1, 2, 3, 4, 5]))  # prints the root of the created BST

This drill exercises all the necessary concepts and builds up to the final solution. Each concept is demonstrated in isolation and then integrated into the final solution.