Devin's Blog

Convert Sorted Array to Binary Search Tree

2 min read

Related: Balanced Binary Tree Construct Binary Tree from Preorder and Inorder Traversal

Info

This solution is currently , since you are

Intuition

  • Where I got messed up here was the mid vs. mid + 1.
  • Since I read Construct Binary Tree from Preorder and Inorder Traversal, I thought that in this solution from Neetcode, he used up to and including mid + 1 when setting the left side of the tree. However, this is not the case since you don’t want to consider the root node when going down the subtree.
  • That is to say, mid = (left + right) // 2 always picks the right hand side (the greater value) since indices are 0-indexed. And therefore, the left side of a given partition will always be the remaining element in the last partition.

Code

# 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 r(left, right):
            if left > right:
                return None
 
            # Choose left middle node as root
            middle = (left + right) // 2
            node = TreeNode(nums[middle])
            node.left = r(left, middle - 1)
            node.right = r(middle + 1, right)
            return node
 
        return r(0, len(nums) - 1)

Passing Array

# 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
 
        left = 0
        right = len(nums) - 1
        mid = (left + right) // 2
 
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid + 1:])
        return node

Notes

References

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

Graph View