Reconstruct a binary tree from a preorder traversal with markers - Alternative Solution (Python)

binary_tree_from_preorder_inorder.py

# Alternative python solution for 9.12 Reconstruct a binary tree from a preorder traversal with markers on EPI (Elements of Programming Interviews)) (September 2018 edition)
# Time complexity: O(n)
# Space complexity: O(n + h) - the size of the hash table plus the maximum depth of the function call stack

class BstNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
    def __repr__(self):
        return f'{self.data} ({self.left}, {self.right})'

    
def binary_tree_from_preorder_inorder(preorder, inorder):
    def build_tree(pre, in_start, in_end):
        if (in_start > in_end):
            return None 

        in_root = inorder_indexes[preorder[pre]]
        left_number_nodes = in_root - in_start

        left = build_tree(pre + 1, in_start, in_root - 1)
        right = build_tree(pre + left_number_nodes + 1, in_root + 1, in_end)

        return BstNode(preorder[pre], left, right)

    inorder_indexes = {item: idx for idx, item in enumerate(inorder)} # O(n) time

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


inorder = ['F', 'B', 'A', 'E', 'H', 'C', 'D', 'I', 'G']
preorder = ['H', 'B', 'F', 'E', 'A', 'C', 'D', 'G', 'I']
print(binary_tree_from_preorder_inorder(preorder, inorder))