Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Recreation of a binary tree from pre and post-order sequentialisations.
"""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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.