How do I construct a non-binary tree based on the preorder&inorder or postorder&inorder traversal?

Question

Two of the exercises for my Data Structures and Algorithms class sound like this

Construct the tree whose preorder traversal is: 1, 2, 5, 3, 6, 10, 7, 11, 12, 4, 8, 9, and inoder traversal is 5, 2, 1, 10, 6, 3, 11, 7, 12, 8, 4, 9.

Construct the tree whose postorder traversal is: 5, 2, 10, 6, 11, 12, 7, 3, 8, 9, 4, 1, and inoder traversal is 5, 2, 1, 10, 6, 3, 11, 7, 12, 8, 4, 9.

I only have to draw the structure of the tree, without implementing it in a programming language. The thing that makes this tasks harder is that the trees are not binary trees. What techniques could I use to build the trees?

Answer 1

I'm not sure I can give a precise algorithmic solution to this, but I can give a conceptual one that should be sufficient. I think if you could fine-tune it to a well-defined algorithm it would be useful for you and make (that part of) the midterm trivial.

First, think about how an inorder traversal traverses a tree. If you draw the tree so that the leftmost child is to the left (visually) and the other children are to the right (visually) then the inorder traversal loosely goes from left to right. You might run into an issue where it's not quite left to right (because of some overlap between a child of one node and the parent or something like that) but you can always stretch the tree out to make it clearly "left to right". So I take advantage of that by starting my tree with the inorder traversal:

5 2 1 10 6 3 11 7 12 8 4 9

Then the idea is we move nodes up and down according to the preorder traversal. This part is the hard to define part. Basically you move nodes up if they're visited "earlier" and move them down if they're visited later. So, for instance, 1 is to the left of 2 and 5 in the preorder traversal so I raised it "up" in the sense that I made 2 and 5 ancestors (but not necessarily children) of 1. So something like

   1
5 2 10 6 3 11 7 12 8 4 9

Then you see the 2 which comes before the 5, so I raised 2:

    1
  2 
5     10 6 3 11 7 12 8 4 9

Then you see a 3 comes before the 6 and 10 in the preorder traversal so we can "raise" it.

    1
  2        3
5     10 6   11 7 12 8 4 9

And so on. Note that the 3 could eventually be a child of 2 or 1... the tree that satisfies the above constraints isn't unique.