ConvertSortedArrayToBST

Problem

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

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:sup:`4`

• -10:sup:`4`<= nums[i] <= 10:sup:`4`

• nums is sorted in a strictly increasing order.

Solution

A balanced binary tree will have the middle element of nums as the root, the 1/4 and 3/4 elements as the left and right children, and so on. Find the middle element of nums and divide nums into two halves. Repeat on the left half to form the left subtree and the right half to form the right subtree.

Pattern

Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

Code

from typing import List


class TreeNode:
    """Node in a binary tree.
    """

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


def sortedArrayToBST(nums: List[int]) -> TreeNode | None:
    """Convert the sorted array ``nums`` to a balanced binary search tree.
    """
    if len(nums) == 0:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid + 1:])
    return root


def tree2list(root: TreeNode | None) -> List[int]:
    """Convert a binary tree preorder to a list.
    """
    if root is None:
        return []
    else:
        return [root.val] + tree2list(root.left) + tree2list(root.right)

Test

>>> from ConvertSortedArrayToBST import sortedArrayToBST, tree2list
>>> root = sortedArrayToBST([-10, -3, 0, 5, 9])
>>> tree2list(root)
[0, -3, -10, 9, 5]
>>> root = sortedArrayToBST([1, 3])
>>> tree2list(root)
[3, 1]

class ConvertSortedArrayToBST.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

ConvertSortedArrayToBST.sortedArrayToBST(nums: List[int]) → TreeNode | None

Convert the sorted array nums to a balanced binary search tree.

ConvertSortedArrayToBST.tree2list(root: TreeNode | None) → List[int]

Convert a binary tree preorder to a list.