Recreation of a binary tree from pre and post-order sequentialisations.

tree_reconstruction.py

"""Recreation of a binary tree from pre and post-order sequentialisations.

There are no constraints or expectations of explicit ordering. The algorithm
runs in linear time and storage space, with a small stack that is dependent
on the height of the tree.
"""

def recreate_tree(pre_order, in_order):
    print(f"\nStack recreating tree from PO {pre_order} and IO {in_order}")
    pre_order_iter = iter(pre_order)
    node_value = next(pre_order_iter)
    tree = Tree()
    tree.root = cursor = Node(node_value)
    node_stack = [(None, None), (node_value, cursor)]
    right = node_value == in_order[0]

    for io_value in in_order:
        print(f"\nProcessing in-order value {io_value}, stack: {node_stack}")
        if io_value == node_stack[-1][0]:
            _node_value, cursor = node_stack.pop()
            print(f"- occurred in stack, going up tp {cursor}!")
            continue

        print(f"- in-order value {io_value} is a new target!")
        for node_value in pre_order_iter:
            if right:
                print(f"- appending {node_value} to right of {cursor}")
                cursor.right = cursor = Node(node_value)
                right = False
            else:
                print(f"- appending {node_value} to left of {cursor}")
                cursor.left = cursor = Node(node_value)
            if node_value == io_value:
                right = True
                break
            node_stack.append((node_value, cursor))
    return tree