When Inorder traversing a tree resulted E A C K F H D B G, what would be the preorder equivalent?
I am having trouble drawing this tree because I do not know when to put a value to right or left of a tree because it consists of letters.
How do I determine this?
Edited to add: I am given the following choices as possible preorder traversals:
A. F A E K C D B H G
B. F A E K C D H G B
C. E A F K H D C B G
D. F E A K D C H B G
Answer
There are multiple preorder equivalents of this inorder traversal. You cannot tell from just the letters what the original tree structure was, because there are no parenthesis grouping the letters.
For example, here are two possible trees which would produce the inorder traversal you stated but have different preorder traversals. There are many others.
Inorder: E A C K F H D B G
Preorder: F K A E C D H B G
Inorder: E A C K F H D B G
Preorder: K A E C H F D G B
UPDATE
Per your comments I see that this is actually some kind of test or homework problem. Since you are given both the inorder traversal AND some possible preorder traversals, the question becomes, can we reconstruct a tree that will satisfy both orderings? It turns out that yes, this is definitely quite doable; you just have try each one and puzzle it out.
So how should we approach this? Well, what do we know about inorder and preorder traversals?
We know that an inorder traversal gives the absolute ordering of the nodes left to right over the tree. Conversely, a preorder traversal lists out the nodes starting from the root going downward, always listing the current node first, then the left subtree, then the right subtree. So one approach would be to walk through the preorder traversal (since the first letter gives us the root node), and try to add each node to a tree, using the inorder traversal as a guide to decide whether we should place that node to the left or right of the previous one.
It doesn't matter which answer we start with, so let's try answer (D) first: F E A K D C H B G
Start by placing the root node, F:
FThe next node, E, connects to F, obviously, but is it left or right? Let's look at the inorder traversal. Does E come before or after F? It comes before, so that means it has to be the left node.
F / ENext we have A. There are three open spots in the tree now: left of E, right of E, and right of F. In the inorder traversal, A comes after E but before F. So that means it has to be right of E.
F / E \ AK comes next in the preorder. Where should it go in the tree? The inorder says K comes after A but before F. Of the 3 open spots in the tree that are consistent with the preorder (left of A, right of A, or right of F), the only place it can fit is right of A.
F / E \ A \ KD is next. The inorder traversal says D must come after F, and there's only one open spot in our tree that works for that: right of F.
F / \ E D \ A \ KNow here's where we run into trouble. The next node to place is C, according to the preorder. According to the inorder, C must come before K and after A, which means placing it left of K. But, we can't do that because that would change the preorder! Remember that preorder goes top to bottom, left to right, so every new node placed either has to go directly below the last node placed, or above and to the right of it in the tree. The last node we placed was D, which means C would have to be connected to it to satisfy the preorder. But if C is connected to D, it can't be connected to K. So we have a contradiction. That means that answer (D) is not the correct solution.
Hopefully now you see how to walk through the traversals and build trees from them. I will leave it to you to try the other three answers and figure out which of them is correct.