Convert Sorted Array to Binary Search Tree — LeetCode 108 Python Solution

The problem

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

Example

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:

Python 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 dfs(l: int, r: int) -> Optional[TreeNode]:
            if l > r:
                return None
            mid = (l + r) >> 1
            return TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r))

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

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 108. Convert Sorted Array to Binary Search Tree is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Tree, Binary Tree and Binary Search Tree.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems