October 18, 2013
In a previous exercise, we wrote a small library for maintaining binary search trees, including a function that traversed the tree in order. In today’s exercise we will write functions that traverse a tree in pre-order and post-order.
Given the tree shown at right, a pre-order traversal visits the node in this order: 8 3 1 6 4 7 10 14 13. At each level of the tree, pre-order traversal first handles the current node, then calls itself recursively on the left child, then calls itself recursively on the right child.
A post-order traversal visits the nodes in this order: 1 4 7 6 3 13 14 10 8. At each level of the tree, post-order traversal calls itself recursively on the left child, then calls itself recursively on the right child, then finally handles the current node.
In addition to traversing a tree in pre-order or post-order, you should write functions that reconstruct the original tree given a list of the tree nodes in pre-order or post-order.
Your task is to write the four functions described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.