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_value_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_value_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])+']'

from ListBinaryTree import ListBinaryTree

def buildTree(inorder,preorder):

# YOUR IMPLEMENTATION

def postorder(tree):

# YOUR IMPLEMENTATION

def main():

print("Binary Tree construction:")

inorder = input("Please enter the inorder sequence: ")

preorder = input("Please enter the preorder sequence: ")

tree =[]

if (len(inorder) != len(preorder)):

print("Error: Input strings have different length")

exit(-1)

tree = buildTree(inorder,preorder)

print(tree)

print("Postorder sequence of tree is:",postorder(tree))

main()

Python

Q4. Constructing a Binary Tree (40 Marks) In this exercise we develop a method to reconstruct a binary tree from an inorder and postorder traversal sequence of the unknown tree, as well as provide the postorder traversal sequence of the tree Please complete the program ReconstructTree.py, which lets the user enter the inorder and postorder traversal sequences of a tree as input arguments into the function buildTree (. The function then constructs the corresponding binary tree. The program also needs to include the function postorder), which returns the postorder traversal sequence of an input tree 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 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 1StBinary Tree-pY All of your own implementations should be contained within ReconstructTree.py The following figures show test cases and expected output of the program Binary Tree construction: Please enter the inorder sequence: 42513 Please enter the preorder sequence: 12453 1, [2, [4, None, None], [5, None, None]], [3, None, None]] Postorder traversal of tree is: 45231 Binary Tree construction: Please enter the inorder sequence: CS105 Please enter the preorder sequence: 0SC15 [0, [S, [C, None, None], [1, None, None]], [5, None, None]] Postorder traversal of tree is: C1S50 Binary Tree construction: Binary Tree construction: Please enter the inorder sequence: cbdae Please enter the preorder sequence: abcde [a, [b, [c, None, None], [d, None, None]], [e, None, None]] Postorder traversal of tree is: cdbea Q4. Constructing a Binary Tree (40 Marks) In this exercise we develop a method to reconstruct a binary tree from an inorder and postorder traversal sequence of the unknown tree, as well as provide the postorder traversal sequence of the tree Please complete the program ReconstructTree.py, which lets the user enter the inorder and postorder traversal sequences of a tree as input arguments into the function buildTree (. The function then constructs the corresponding binary tree. The program also needs to include the function postorder), which returns the postorder traversal sequence of an input tree 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 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 1StBinary Tree-pY All of your own implementations should be contained within ReconstructTree.py The following figures show test cases and expected output of the program Binary Tree construction: Please enter the inorder sequence: 42513 Please enter the preorder sequence: 12453 1, [2, [4, None, None], [5, None, None]], [3, None, None]] Postorder traversal of tree is: 45231 Binary Tree construction: Please enter the inorder sequence: CS105 Please enter the preorder sequence: 0SC15 [0, [S, [C, None, None], [1, None, None]], [5, None, None]] Postorder traversal of tree is: C1S50 Binary Tree construction: Binary Tree construction: Please enter the inorder sequence: cbdae Please enter the preorder sequence: abcde [a, [b, [c, None, None], [d, None, None]], [e, None, None]] Postorder traversal of tree is: cdbea