Skip to content

Instantly share code, notes, and snippets.

@lopespm
Created May 10, 2019 17:30
Show Gist options
  • Save lopespm/1a256505da7ab94b8326714c61256583 to your computer and use it in GitHub Desktop.
Save lopespm/1a256505da7ab94b8326714c61256583 to your computer and use it in GitHub Desktop.
Reconstruct a binary tree from a preorder traversal with markers - Alternative Solution (Python)
# 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment