LC 0108 [E] Convert Sorted Array to Binary Search Tree

- -  -  - -
(L)  M  (R)

https://www.youtube.com/watch?v=0K0uCMYq5ng&ab_channel=NeetCode

# 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 binarysplit(l, r):
            if l > r: # not l <= r (recursion base case opposite of binary search while l <= r)
                return None
            
            m = (l + r) // 2
            root = TreeNode(nums[m])
            root.left = binarysplit(l, m - 1)
            root.right = binarysplit(m + 1, r)
            return root
        
        return binarysplit(0, len(nums) - 1)

overly complicated Omkar 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def helper(P, startP, endP, I, startI, endI):
            if startP > endP: return None
            rootnode = TreeNode(P[startP])
            rootindex = hashmap[P[startP]]
            numleft = rootindex - startI
            numright = endI - rootindex
            rootnode.left = helper(P, startP + 1, startP + numleft, I, startI, rootindex - 1)
            rootnode.right = helper(P, startP + numleft  +1, endP, I, rootindex + 1, endI)
            return rootnode
        
        inorder_value_to_index = {}
        for i in range(len(inorder)):
            inorder_value_to_index[inorder[i]] = i
        return helper(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)
    
            
'''
top-down tree construction

            rootnode
            startP  numleft         numright    endP
Preorder:   x       [Preorder(L)]   [Preorder(R)]
Inorder:    [Inorder(L)]    x           [Inorder(R)]
            startI numleft  rootindex   numright   endI
            
if we lookup x in Inorder, we can find Inorder numleft and numright
and since Preorder(L) has same length as Inorder(L), if we now Inorder numleft and numright then we also know Preorder numleft and numright
'''