In this exercise we develop a method to reconstruct a binary

In this exercise we develop a method to reconstruct a binary tree from an inorder and postorder traversal sequence of the unknown tree. lease write a program ReconstructTree.py, which lets the user input the inorder and postorder traversal sequences and from this reconstructs the corresponding binary tree and outputs it printO method. using the

Solution

ListBinaryTree.py

class ListBinaryTree:
   \"\"\"A binary tree class with nodes as lists.\"\"\"
   DATA = 0    # just some constants for readability
   LEFT = 1
   RIGHT = 2

   def __init__(self, root_value, left=None, right=None):
       \"\"\"Create a binary tree with a given root value
       left, right the left, right subtrees      
       \"\"\"  
       self.node = [root_value, left, right]
      
   def create_tree(self, a_list):
       return ListBinaryTree(a_list[0], a_list[1], a_list[2])

   def insert_left(self, value):
       \"\"\"Inserts value to the left of this node.
       Pushes any existing left subtree down as the left child of the new node.
       \"\"\"
       self.node[self.LEFT] = ListBinaryTree(value, self.node[self.LEFT], None)

   def insert_right(self, value):
       \"\"\"Inserts value to the right of this node.
       Pushes any existing left subtree down as the left child of the new node.
       \"\"\"    
       self.node[self.RIGHT] = ListBinaryTree(value, None, self.node[self.RIGHT])

   def insert_tree_left(self, tree):
       \"\"\"Inserts new left subtree of current node\"\"\"
       self.node[self.LEFT] = tree

   def insert_tree_right(self, tree):
       \"\"\"Inserts new left subtree of current node\"\"\"
       self.node[self.RIGHT] = tree

   def set_value(self, new_value):
       \"\"\"Sets the value of the node.\"\"\"
       self.node[self.DATA] = new_value

   def get_value(self):
       \"\"\"Gets the value of the node.\"\"\"
       return self.node[self.DATA]

   def get_left_subtree(self):
       \"\"\"Gets the left subtree of the node.\"\"\"
       return self.node[self.LEFT]

   def get_right_subtree(self):
       \"\"\"Gets the right subtree of the node.\"\"\"
       return self.node[self.RIGHT]

   def __str__(self):
       return \'[\'+str(self.node[self.DATA])+\', \'+str(self.node[self.LEFT])+\', \'+\\
   str(self.node[self.RIGHT])+\']\'

  
ReconstructTree.py

from ListBinaryTree import ListBinaryTree

def display_intro():
    UPI = \"jpet954\"
    message = \"Binary Tree reconstructed by \" + UPI
    print(message)

def inorder_ans():
    answer = input(\"Please enter the inorder sequence: \")
    return answer

def postorder_ans():
    answer = input(\"Please enter the postorder sequence: \")
    return answer

def build_tree(inorder, postorder):
    if len(inorder) == 0:
        return None
    if len(inorder) == 1:
        return ListBinaryTree(inorder[0])
    root = ListBinaryTree(postorder[len(postorder) - 1])
    index = inorder.index(postorder[len(postorder) - 1])
    root.left = root.insert_tree_left(build_tree(inorder[0:index], postorder[0:index]))
    root.right = root.insert_tree_right(build_tree(inorder[index+1 : len(inorder)], postorder[index : len(postorder)-1]))
    return root

def main():
    display_intro()
    inorder_tree = inorder_ans()
    postorder_tree = postorder_ans()
    tree = build_tree(inorder_tree,postorder_tree)
    print(tree)
main()