Created
October 20, 2020 22:25
-
-
Save edelooff/730266c093664b9bed127919239e3c50 to your computer and use it in GitHub Desktop.
Recreation of a binary tree from pre and post-order sequentialisations.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"""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