Skiena Problem 7-8

[learner-long-life]

This problem was assigned in [Readings 04]() but was much more difficult than I realized.

This is a tree I considered

graph TD
    17--->9
    17--->24
    9--->5
    9--->13
    24--->21
    24--->29

with

In-order Traversal

5 9 13 17 21 24 29

Pre-Order Traversal

17 9 5 13 24 21 29

I'm proposing a recursive solution with a stack, and two pointers, one in the in-order traversal and one in the pre-order traversal.

The pseudocode looks something like this (it's not fully worked out).

1. Start in the pre-order traversal and push onto stack until you reach the same starting (leftmost, or least) element in the in-order traversal. That's 5 in the example above.
2. Consider the last two elements in both traversals. 2a. If they contain the same elements in possibly different orders, do the following 5 9 in the in-order traversal and 9 5 in the pre-order traversal. They are in reverse order of each other, which means the lesser one is the left child of the greater one. Build this tree

Delete 5 and 9 from both traversals, and put the tree in their place (just one slot). 2b. If they do not contain the same two elements (but the same first element), push the same first element onto a stack, and go back to Step 2 with the next two elements.

4. Go back to step 2 and repeat until there is only one element left in both traversals, and it's the fully built tree.

My working theory is that it's always possible to reconstruct the same tree given both in-order and pre-order traversal.

By similar algorithm, I believe it's possible to do the same with any two traversals, such as the second part of the problem states.

[learner-long-life]

We denote (A,B,C) to mean the 3-node subtree

graph TD
    A--->B
    A--->C

(5,9) 13 17 21 24 29
17 (5,9) 13 17 24 21 29

(5,9,13) 17 21 24 29
17 (5,9,13) 17 24 21 29

((5,9,13), 17) 21 24 29
((5,9,13), 17) 24 21 29

((5,9,13), 17) (21,24) 29
((5,9,13), 17) (21,24) 29

((5,9,13), 17) (21,24,29)
((5,9,13), 17) (21,24,29)

((5,9,13), 17, (21,24,29))
((5,9,13), 17, (21,24,29))

I think whenever we encounter the same first element but different second elements in the two traversals, we should come back to the first element (maybe push it onto a stack?) but move on to the 21 and 24 and complete building the right subtree.

[learner-long-life]

There is a much simpler recursive solution that I read, that shares the same in-order traversal and pre-order traversal list among all calls, splits the in-order traversal in each recursive call by slicing or start/end indices, and pops the front of the pre-order traversal, depending on popping for the parent first, then recursively calling the left child before the right child,

A similar solution for post-order traversal + in-order traversal would be identical except recursively calling the left and right children first, then popping for the parent from the post-order traversal afterwards.