Tree Creation Via Traversal Output

[Ecurb]

Hi, I'm familiar with tree traversal alogirthms, post,pre and in-order. If you give me a tree I can print out the specified traversal of that tree. However, one thing I can't do is build a tree from a given output. For example, on my last test, my prof gave me this Question:

A pre-order of a binary tree produced: ADFGHKLPQRWZ
A post order traversal of the same tree produced: GFHKDLAWRQPZ
Draw the binary tree.

How do you build a tree using two given traversal outputs?

 

[Coin]

Hm, I don't know of a specific algorithm or method for doing this but I don't think it should be that hard.

Just consider what the pre and post order sequences tell you about where nodes are in relation to each other.

I would suggest starting with the two most obvious pieces of information the pre and post order tell you:

- The root is A (first letter of preorder)
- The leftmost node is G (first letter of postorder)

If it were me I would try drawing those two letters on a piece of paper and then try to fit in the rest of the letters one by one...