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:
Do the recursion before building the new tree. So, your list would look like this:
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 +<--+ +---+