Convert Preorder listing of a binary tree to postorder and vice versa

Question

How can I find the preorder listing of a tree if only the postorder listing is given and vice versa. Also, in the tree, every non-leaf node has two children (i.e. Each node has either two or zero children.)

EDIT: Another given assumption is that the label of each node is unique and has a field that will identify it as an internal node or a leaf. I think that ought to get rid of the ambiguity of a single preorder or postorder being able to uniquely identify a tree.

Answer 1

Without assuming that nodes in the tree have a field that idenrify themselves as internal or leaf, you can't find a unique answer for your question. That assumption or inorder listing must be available to find a unique tree. In this case, to find one possible answer, you can construct a tree of the form shown below to match any given postorder listing: (suppose postorder listing is: 1 2 3 4 5 6 7 8 9)

9[7[5[3[1,2],4],6],8]

Now you can make preorder listing using this tree.

Assuming nodes in the tree have a field that identify themselves as internal or leaf, we can make a unique tree out of a postorder listing for this kind of trees with this algorithm:

1. Sweep from the beginning of the postorder list and find the first internal node. This node will have exactly two leaf children which precede this node in postorder listing.
2. In your tree structure add that internal node and make two preceding nodes in the listing its children.
3. Remove those two children from listing and make that internal node a leaf.
4. Go to step 1 and repeat until listing becomes empty.

Answer 2

Consider the recursive structure of a preorder traversal:

T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r

Then we know that the root of a tree described by T(r) is always the first node in the traversal.

Knowing this, and knowing that a root is always higher in a tree than its subtrees, think about how you would use this information to rebuild the tree. Think recursively.

Caveat: this can only be done if this is a binary search tree, which constrains nodes such that left-child < root < right-child. In general, trees cannot be reconstructed from a single traversal. See this excellent resource for a more detailed explanation.

Ambiguity still exists regardless of the rule about 0 or 2 children:

    4
   / \
  2   5
 / \ / \
 1 3 6 7

    4
   / \
  2   7
 / \
1   3
   / \
  5   6

Both have the preorder traversal [4 2 1 3 5 6 7]