9.12 using queue for simpler solution for Reconstruct a binary tree from traversal data

#1

Hello,

I think I can get away from keeping preorder_start and preorder_end arguments if I use queue of preorder list to popleft the root element of the sub tree during in the recursion call. It doesn’t change the the time and space complexity. Please let me know your thought on it.

def binary_tree_from_preorder_inorder(preorder: List[int],
                                      inorder: List[int]) -> BinaryTreeNode:
    node_to_inorder_idx = {data: i for i, data in enumerate(inorder)}
    def f(left: int, right: int):
        if left > right:
            return None
        elem = preorder.popleft()
        idx = node_to_inorder_idx[elem]
        tree = BinaryTreeNode(elem, f(left, idx - 1), f(idx + 1, right))
        return tree

    preorder = collections.deque(preorder)
    return f(left=0, right=len(inorder) - 1)
0 Likes