how to build a binary tree from preorder and inorder traversals

Question

Im doing an assignment on building a binary tree from the preorder and inorder traversals (a char in each Node) and im trying to wrap my brain around how to build the actual tree.

Here is my thought process on how to accomplish this:

1. store the first entry in the preorder as the root node
2. search the inorder for that entry.
3. take the chars to the left of the root node and save them as a char array.
4. take the chars to the right of the root node and save them as a char array.
5. make a new tree, with the root as the parent and its 2 children being the left and right char arrays.
6. keep going recursively until the preorder length is 0.

I have steps 1-4 taken care of, but im not too sure how to properly build my tree, and was wondering if anyone had any pointers. Thank you.

Solution

Do the recursion before building the new tree. So, your list would look like this:

1. If the arrays have length 1, just return a leaf node with this single item in it. (This is the recursion foundation.) (O(1))
2. Store the first entry in the preorder array as the root node. (O(1))
3. Search the inorder array for that entry. (O(n))
4. Take the chars to the left of the root node in the inorder array and save them as a char array. Take the same amount of characters from the preorder array (after the root). (O(n), or O(1) when just throwing pointers/indexes around.)
5. Take the chars to the right of the root node and save them as a char array. Take the same amount of characters from the preorder array (after the first part – that should be just the remainding part). (O(n), or O(1) when just throwing pointers/indexes around.)
6. Recursively make a tree from both left char arrays.
7. Recursively make a tree from both right char arrays.
8. Combine both trees with your root node. (O(1).)

The non-recursive parts can be done in O(n) overall, and summing them up for each recursion level is also O(n) each. The total runtime thus depends on the number of recursion levels. If you have a approximately balanced tree, the depth is O(log n), thus we get to O(n · log n) at all. As the only necessarily slow part is the search of the root node in the inorder array, I guess we could optimize that even a bit more if we know more about the tree.

In the worst case we have one recursion level for each node in the tree, coming to complexity O(n·n).

Example: Preorder ABCDEF, Inorder FEDCBA, Tree:

                                   +---+
                                   | A |
                                   ++--+
                                    |
                            +---+   |
                            | B +<--+
                            ++--+
                             |
                     +---+   |
                     | C +<--+
                     ++--+
                      |
              +---+   |
              | D +<--+
              ++--+
               |
       +---+   |
       | E +<--+
       ++--+
        |
+---+   |
| F +<--+
+---+

Comments

[Andre Artus]

This is a pretty cool method. But you will have to partition both the in-order and pre-order sequences, no?

[Paŭlo Ebermann]

Yes, seems so. I think this is easy, since you can get the partition sizes for the preorder from the inorder partition.

[Andre Artus]

You are right, it is easy. One just needs to ensure that the partitioning is done correctly. Your way is the easiest way to do it on paper.

[Ahmed Ashour]

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review

[gariepy]

@AhmedAshour: I disagree...this isn't a link-only answer. Andre has given a [short] description of his solution, and then a link to a code example. Just because an answer is short, and has a link, doesn't automatically make it a link only answer. See: meta.stackoverflow.com/questions/287563/…

[Andre Artus]

@AhmedAshour, The link is to a page on SO. The problem with most "link-only" is potential dead links. If that link dies then this page likely dead too.

[KGhatak]

@Paŭlo Ebermann - Is the run time better than O(n*n) ? n=total number of nodes in the tree

[Paŭlo Ebermann]

@BuckCherry I don't have a proof and I'm currently not in the mood for actually creating one. I would guess the best case (balanced tree) is something like O(n· log n). Worst case will likely be O(n²) (something like just a linked list, i.e. where the root node is always last in the search).