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...

 

[quicknote]

Building a tree using two given traversal outputs can be done by following a specific set of steps and using the properties of pre-order and post-order traversals.

Firstly, we need to understand that the root node of a binary tree will always be the first element in a pre-order traversal and the last element in a post-order traversal.

In this given example, we can see that the first element in the pre-order traversal is "A" and the last element in the post-order traversal is also "A". This means that "A" is the root node of our binary tree.

Next, we can divide the remaining elements in the pre-order traversal into two parts - left subtree and right subtree. The elements in the left subtree will be the elements that come before the root node "A" in the pre-order traversal, while the elements in the right subtree will be the elements that come after the root node "A" in the pre-order traversal.

Similarly, we can also divide the remaining elements in the post-order traversal into two parts - left subtree and right subtree. The elements in the left subtree will be the elements that come before the root node "A" in the post-order traversal, while the elements in the right subtree will be the elements that come after the root node "A" in the post-order traversal.

Now, we can repeat the above steps for each subtree, using the elements in the pre-order and post-order traversals to determine the root node and the elements in the left and right subtrees. This process will continue until we have built the entire binary tree.

In this particular example, we can see that the left subtree of "A" will have the elements "DGFHK" in the pre-order traversal and "GFHKD" in the post-order traversal. Similarly, the right subtree of "A" will have the elements "LPQRWZ" in the pre-order traversal and "LAWRQPZ" in the post-order traversal.

By following these steps, we can successfully build the binary tree using the given pre-order and post-order traversals. This process can also be applied to other types of tree traversal outputs, such as in-order traversal.