https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ the best way to solve this is to draw out the tree and both inorder & preorder arrays. 0 ms, beats 100% runtime. 19 mb, beats 67% memory.

construct_binary_tree_optimised.py

# 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]) -> Optional[TreeNode]:
        # build hashmap of indices
        num_to_inorder_idx: dict[int, int] = {num: idx for idx, num in enumerate(inorder)}

        num_nodes = len(preorder)

        # inorder_right, preorder_right is exclusive
        def divide_and_conquer(curr: int, inorder_left: int, inorder_right: int, preorder_left: int, preorder_right: int):
            # base cases
            if inorder_right - inorder_left == 0:
                # empty child leaf node
                return None

            if inorder_right - inorder_left == 1:
                # single child leaf node
                return TreeNode(val=inorder[inorder_left])

            # divide inorder, using hashmap to find index quickly
            # split inorder into left array and right array using curr_idx
            curr_idx = num_to_inorder_idx[curr]

            # divide preorder
            preorder_mid = preorder_left + (curr_idx - inorder_left)

            # create TreeNode here, but actually this is a minor optimization
            curr = TreeNode(curr)

            if preorder_mid - preorder_left > 0:
                # fixed: inefficient to create TreeNode() here. it should be done inside the fn
                curr.left = divide_and_conquer(
                    preorder[preorder_left],
                    inorder_left,
                    curr_idx,
                    preorder_left + 1,  # add 1 bcos we used `preorder_left`
                    preorder_mid
                )

            if preorder_right - preorder_mid > 0:
                curr.right = divide_and_conquer(
                    preorder[preorder_mid],
                    curr_idx + 1,
                    num_nodes,
                    preorder_mid + 1,  # add 1 bcos we used `preorder_mid`
                    preorder_right
                )
            
            return curr

        return divide_and_conquer(preorder[0], 0, num_nodes, 1, num_nodes)

runtime is O(N) since we must create a new TreeNode per node, so total number of function calls is O(N). each function call only does O(1) work.

worst case recursion depth is O(N) if tree is perfectly imbalanced (linked list). best case recursion depth is O(logN) if tree is perfectly balanced. O(N) memory cost for building hashmap of node values to indices.