Convert Sorted Array to Binary Search Tree

 

  1. Clarify the problem:

    • The problem requires converting a sorted array into a binary search tree (BST).
    • We need to implement a function that takes a sorted array as input and returns the root node of a BST constructed from the array.

  2. Analyze the problem:

    • Input: A sorted array of integers.
    • Output: The root node of a binary search tree.
    • Constraints: None given.

  3. Design an algorithm:

    • To construct a balanced BST from a sorted array, we can use a recursive approach.
    • We will define a recursive helper function that takes the left and right indices of the current subarray as input.
    • In each recursive call, we will find the middle element of the subarray and use it as the value of the current node.
    • We will recursively construct the left subtree using the left half of the subarray and the right subtree using the right half of the subarray.
    • The base case for the recursion is when the left index becomes greater than the right index, indicating an empty subarray.
    • We will return the root node of the constructed BST.

  4. Explain your approach:

    • We will define a recursive helper function called buildBST that takes the left and right indices of the current subarray as input.
    • In each recursive call, we will find the middle index of the subarray by calculating (left + right) // 2.
    • We will create a new TreeNode with the value at the middle index as the node's value.
    • We will recursively call buildBST to construct the left subtree using the left half of the subarray (from left to mid-1).
    • We will recursively call buildBST to construct the right subtree using the right half of the subarray (from mid+1 to right).
    • We will assign the left and right subtrees to the left and right attributes of the current node, respectively.
    • The base case for the recursion is when the left index becomes greater than the right index, in which case we return None.
    • Finally, we will call the buildBST function with the initial left and right indices (0 and len(nums) - 1, respectively) and return the root node.

  5. Write clean and readable code:

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

def sortedArrayToBST(nums):
    def buildBST(left, right):
        if left > right:
            return None

        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = buildBST(left, mid - 1)
        root.right = buildBST(mid + 1, right)

        return root

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

  7. Test your code:

    python
  8. # Test case 1
nums = [-10, -3, 0, 5, 9]
# The sorted array: [-10, -3, 0, 5, 9]
# The resulting BST:
#        0
#      /   \
#    -3     9
#   /  \
# -10   5
assert sortedArrayToBST(nums).val == 0
assert sortedArrayToBST(nums).left.val == -3
assert sortedArrayToBST(nums).right.val == 9
assert sortedArrayToBST(nums).left.left.val == -10
assert sortedArrayToBST(nums).left.right.val == 5

# Test case 2
nums = [1, 2, 3, 4, 5]
# The sorted array: [1, 2, 3, 4, 5]
# The resulting BST:
#      3
#    /   \
#   2     5
#  / \
# 1   4
assert sortedArrayToBST(nums).val == 3
assert sortedArrayToBST(nums).left.val == 2
assert sortedArrayToBST(nums).right.val == 5
assert sortedArrayToBST(nums).left.left.val == 1
assert sortedArrayToBST(nums).left.right.val == 4

  9. Optimize if necessary:

    • The provided solution has a time complexity of O(n), where n is the number of elements in the sorted array. This is because we visit each element once.
    • There is no further optimization possible for this problem.

  10. Handle error cases:

    • The given code assumes that the input nums is a valid sorted array. If the input is not a valid sorted array, the resulting BST may not be constructed correctly.

  11. Discuss complexity analysis:

    • The time complexity of the solution is O(n), where n is the number of elements in the sorted array. We visit each element once to construct the BST.
    • The space complexity is O(log n) on average, as the recursion depth is limited by the height of the balanced BST. In the worst case, when the input array is sorted in ascending or descending order, the space complexity is O(n) as the resulting BST will be skewed.
Next Post Previous Post