To the binary tree program, you are to add a function that performs a post order traversal of the tree. (This is what is provided as input to create a tree.) This means that if you are at a node, add the traversal of the left node to the string, then the traversal of the right node to the string, then the node itself. After writing the function, write a
__main__ program that constructs a tree, and then compares the postorder traversal generated by your function to the string used to create it. They should match.
def postorder(tree, carryover=""):
if tree.left != None:
carryover = postorder(tree.left, carryover)
if tree.right != None:
carryover = postorder(tree.right, carryover)
if carryover != "":
carryover += " " + tree.data
else:
carryover = tree.data
return carryover
def test(expression, answer):
x = parse(expression)
print x, "=", x.evaluate()
print postorder(x)
assert(postorder(x) == expression)
assert(x.evaluate() == answer)