Last active
December 17, 2017 17:11
-
-
Save ali01/11020531 to your computer and use it in GitHub Desktop.
Reconstruct Binary Tree from In-Order and Post-Order Traversals
This file contains hidden or 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
| #!/usr/bin/env python | |
| class Node(object): | |
| def __init__(self, value): | |
| self.value = value | |
| self.left = None | |
| self.right = None | |
| def reconstruct_binary_tree(in_order, post_order): | |
| '''Reconstructs a binary tree given two integer arrays as arguments: | |
| * in_order -- the tree's pre-order traversal | |
| * post_order -- the tree's post-order traversal | |
| Assumes that in_order and post_order are of the same length and contain | |
| the same set of integers (though in different order) | |
| Returns an object of type Node. | |
| ''' | |
| # base case: traversal lists are empty | |
| if len(in_order) == 0: | |
| return None | |
| # construct the root node | |
| root = Node(post_order[-1]) | |
| # Use the in-order traversal to determine which values belong to the left | |
| # subtree, and which values belong to the right subtree | |
| pivot = in_order.index(root.value) | |
| # recursively compute the left subtree | |
| in_order_left = in_order[0 : pivot] | |
| post_order_left = post_order[0 : pivot] | |
| root.left = reconstruct_binary_tree(in_order_left, post_order_left) | |
| # recursively compute the right subtree | |
| in_order_right = in_order[pivot + 1 :] | |
| post_order_right = post_order[pivot : -1] | |
| root.right = reconstruct_binary_tree(in_order_right, post_order_right) | |
| # return the root of the tree | |
| return root | |
| # -- helper functions (for testing) -- | |
| def in_order_traversal(node): | |
| out = [] | |
| def recursive_helper(node, out): | |
| if node is None: | |
| return None | |
| recursive_helper(node.left, out) | |
| out.append(node.value) | |
| recursive_helper(node.right, out) | |
| recursive_helper(node, out) | |
| return out | |
| def post_order_traversal(node): | |
| out = [] | |
| def recursive_helper(node, out): | |
| if node is None: | |
| return None | |
| recursive_helper(node.left, out) | |
| recursive_helper(node.right, out) | |
| out.append(node.value) | |
| recursive_helper(node, out) | |
| return out | |
| def build_test_tree(): | |
| node_10 = Node(10) # 10 | |
| node_7 = Node(7) # / \ | |
| node_8 = Node(8) # 7 8 | |
| node_3 = Node(3) # / \ / | |
| node_9 = Node(9) # 3 9 6 | |
| node_6 = Node(6) # \ | |
| node_5 = Node(5) # 5 | |
| node_10.left = node_7 | |
| node_10.right = node_8 | |
| node_7.left = node_3 | |
| node_7.right = node_9 | |
| node_8.left = node_6 | |
| node_3.right = node_5 | |
| return node_10 | |
| if __name__ == "__main__": | |
| tree = build_test_tree() | |
| in_order_t = in_order_traversal(tree) | |
| post_order_t = post_order_traversal(tree) | |
| # test in_order_traversal() | |
| assert(in_order_t == [3, 5, 7, 9, 10, 6, 8]) | |
| # test post_order_traversal() | |
| assert(post_order_t == [5, 3, 9, 7, 6, 8, 10]) | |
| # test reconstruct_binary_tree | |
| test_tree = reconstruct_binary_tree(in_order_t, post_order_t) | |
| assert(in_order_traversal(test_tree) == in_order_t) | |
| assert(post_order_traversal(test_tree) == post_order_t) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment