deepSWE.io

Convert Sorted Array to Binary Search Tree

TreesDFS

15 min

Problem Statement

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

Example

Example 1:

Input: nums = [-10,-3,0,5,9]

Output: [0,-3,9,-10,null,5]

Solution: Depth-First Search (DFS)

The problem can be solved efficiently using a recursive Depth-First Search. We can use the fact that the array is sorted to our advantage.

Algorithm Steps

The middle element of the array will be the root of the BST.
The left half of the array will form the left subtree, and the right half will form the right subtree.
Recursively call the function on the left and right halves of the array to build the subtrees.

-10

-3

Processing [-10, -3, 0, 5, 9]. Mid is 0.

Convert Sorted Array to BST Solution


# Definition for a binary tree node.
# 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]:
        
        def helper(l, r):
            if l > r:
                return None
            
            m = (l + r) // 2
            root = TreeNode(nums[m])
            root.left = helper(l, m - 1)
            root.right = helper(m + 1, r)
            return root

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