LeetCode 108: Convert Sorted Array to Binary Search Tree

Recursive

Like binary search, we recursively make mid the root and mid‘s left and right sub-lists the left and right subtrees.

Time: There are $\lg{n}$ levels and due to slicing, each level has $n$ copies. So, like merge-sort, total time is $\mathcal{O}(n \cdot \lg{n})$ .

Space: $\sum{\frac{n}{2^l}} = \mathcal{O}(n)$ .

# 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]:
        if not nums:
            return None
        if len(nums) == 1:
            return TreeNode(nums[0])

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

        left_subtree = self.sortedArrayToBST(nums[ : mid])
        right_subtree = self.sortedArrayToBST(nums[mid+1 : len(nums)])
        
        root.left = left_subtree
        root.right = right_subtree
        return root

Slicing is not necessary, we could pass around (lo, hi) — significantly reducing complexity.

Time: $\sum_{l=0}^{\lg{n}}{2^l} = \mathcal{O}(n)$ .

Space: $\mathcal{O}(\lg{n})$ .

# 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 make_bst(self, nums, lo, hi) -> Optional[TreeNode]:
        if lo > hi:
            return None
        if lo == hi:
            return TreeNode(nums[lo])
        
        mid = (lo+hi) // 2
        root = TreeNode(nums[mid])

        left_subtree = self.make_bst(nums, lo, mid-1)
        right_subtree = self.make_bst(nums, mid+1, hi)

        root.left = left_subtree
        root.right = right_subtree
        
        return root

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.make_bst(nums, 0, len(nums)-1)

Iterative

With an explicit stack we simulate the bottom-up recursion using visited set and nodes dict. Second time we visit a range, on the return path, the TreeNode‘s of the child ranges have already been created.

# 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]:
        if not nums:
            return None
        
        visited = set()
        nodes = {}
        root = (0, len(nums)-1)
        stack = [root]
        while stack:
            u = stack.pop()
            if u not in visited:
                visited.add(u)
                lo, hi = u
                mid = (lo+hi) // 2
                stack.extend( c for c in (u, (lo, mid-1), (mid+1, hi)) if c[0] <= c[1] ) 
                continue
            
            # Return path: u's children are available
            lo, hi = u
            mid = (lo+hi) // 2
            u_node = TreeNode(nums[mid])

            left_subtree = nodes.get((lo, mid-1), None)
            right_subtree = nodes.get((mid+1, hi), None)

            u_node.left = left_subtree
            u_node.right = right_subtree
            
            nodes[u] = u_node

        return nodes[root]

unreasonably effective