Solutions

# First element of preorder is the root. Find the root in inorder, then left subtree is everything to the left of the root in inorder, and right subtree is everything to the right of the root in inorder. Recurse on left and right subtrees.
# trees

# DFS - O(n^2) time, O(n) space
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        if inorder:
            root = TreeNode(preorder.pop(0))
            rootidx = inorder.index(root.val) # O(n) time
            leftsubtree = inorder[:rootidx]
            rightsubtree = inorder[rootidx+1:]
            root.left = self.buildTree(preorder, leftsubtree) # or: preorder[1:rootidx+1] instead of popping
            root.right = self.buildTree(preorder, rightsubtree) # or: preorder[rootidx+1:] instead of popping
            return root

# DFS - O(n) time, O(n) space
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreNode | None:
        inorder_idx = {val: idx for idx, val in enumerate(inorder)}

        preorder_idx = 0

        def dfs(l: int, r: int) -> TreeNode | None:
            nonlocal preorder_idx
            if l > r:
                return

            rootval = preorder[preorder_idx]
            root = TreeNode(rootval)
            mid_idx = inorder_idx[rootval]
            preorder_idx += 1
            root.left = dfs(l, mid_idx-1)
            root.right = dfs(mid_idx+1, r)
            return root

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



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