Skip to content

Instantly share code, notes, and snippets.

@ali01

ali01/btree_reconstruct.py

Last active December 17, 2017 17:11
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ali01/11020531 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ali01/11020531 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ali01 revised this gist Apr 18, 2014. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions btree_reconstruct.py
    View file
    Original file line number Diff line number Diff line change
    @@ -100,13 +100,13 @@ def build_test_tree():

    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()
    in_order_t = in_order_traversal(tree)
    assert(in_order_t == [3, 5, 7, 9, 10, 6, 8])

    # test post_order_traversal()
    post_order_t = post_order_traversal(tree)
    assert(post_order_t == [5, 3, 9, 7, 6, 8, 10])

    # test reconstruct_binary_tree
  2. ali01 revised this gist Apr 18, 2014. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion btree_reconstruct.py
    View file
    Original file line number Diff line number Diff line change
    @@ -99,7 +99,6 @@ def build_test_tree():


    if __name__ == "__main__":
    # test in_order_traversal()
    tree = build_test_tree()
    in_order_t = in_order_traversal(tree)
    post_order_t = post_order_traversal(tree)
  3. ali01 revised this gist Apr 18, 2014. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion btree_reconstruct.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,5 @@
    #!/usr/bin/env python


    class Node(object):
    def __init__(self, value):
    self.value = value
  4. ali01 revised this gist Apr 18, 2014. 1 changed file with 77 additions and 77 deletions.
    154 changes: 77 additions & 77 deletions btree_reconstruct.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,117 +1,117 @@
    #!/usr/bin/env python


    class Node(object):
    def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None
    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:
    '''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
    * 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)
    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.
    '''
    Returns an object of type Node.
    '''

    # base case: traversal lists are empty
    if len(in_order) == 0:
    return None
    # base case: traversal lists are empty
    if len(in_order) == 0:
    return None

    # construct the root node
    root = Node(post_order[-1])
    # 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)
    # 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 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)
    # 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
    # return the root of the tree
    return root



    # -- helper functions (for testing) --

    def in_order_traversal(node):
    out = []
    out = []

    def recursive_helper(node, out):
    if node is None:
    return None
    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.left, out)
    out.append(node.value)
    recursive_helper(node.right, out)

    recursive_helper(node, out)
    recursive_helper(node, out)

    return out
    return out


    def post_order_traversal(node):
    out = []
    out = []

    def recursive_helper(node, out):
    if node is None:
    return None
    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.left, out)
    recursive_helper(node.right, out)
    out.append(node.value)

    recursive_helper(node, out)
    recursive_helper(node, out)

    return 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 = 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
    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
    return node_10


    if __name__ == "__main__":
    # test in_order_traversal()
    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)

    # test in_order_traversal()
    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)
  5. ali01 revised this gist Apr 18, 2014. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions btree_reconstruct.py
    View file
    Original file line number Diff line number Diff line change
    @@ -114,3 +114,4 @@ def build_test_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)

  6. ali01 revised this gist Apr 18, 2014. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion btree_reconstruct.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,5 @@
    #!/usr/bin/env python


    class Node(object):
    def __init__(self, value):
    self.value = value
  7. ali01 created this gist Apr 18, 2014.
    117 changes: 117 additions & 0 deletions btree_reconstruct.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,117 @@
    #!/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__":
    # test in_order_traversal()
    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)