In this exercise we develop a method to reconstruct a binary tree from an inorder and postorder traversal sequence of the unknown tree.

Please 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 using the print() method.

Please note:

- All nodes of the tree contain a single character and the inorder and postorder traversal sequences are strings formed by these characters in the corresponding order.

- You can assume that all characters are different.

- Note that in our examples the reconstructed tree is a binary tree, but not a binary search tree

- Please construct the tree using a list-of-list representation and use the supplied file ListBinaryTree.py

Resources: Supplied File of Code

Examples:

The screenshots below show on the left two examples of the program with input and corresponding output (left). The images on the right show graphical representations of the resulting trees (not required for the assignment).

class ListBinaryTree: "" "A binary tree class with nodes as lists.""m 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 sel f . node [root-value, left, right] def create_tree(self, a_list): return ListBinaryTree(a_list[0], a list[1], alist[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 setvalue(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]