preorder, postorder and reconstruct tree

An interesting problem from mitbbs.com, jobhunting, posted by geniusxyz

The problem is, given two lists, pre and post, representing the preorder and postorder traversal of a general tree, each node in the list is struct {int val; bool is_leaf; }. Reconstruct the tree.

It seems rather difficult and took me a full day.

Some picture always helps, draw a tree and do preorder and postorder to see how nodes are listed.

Observation: we can partition the tree into vertex-disjoint paths, each path starts at some node and ends with a leaf. The pre list gives exactly the paths, each path terminated by a leaf.

Now our job is to attach the paths to the right subtree root, and this follows from post list.

Let's start with attaching the second list to the first list.
Let ptr be the pointer to some node in the first list, init to the leaf. In post list we have ptr matched to the first leaf in post[] in the beginning. Now as long as we have not hit the next leaf in post[], we advance postptr (pointer to post[]) and move ptr to its parent. When we stop, the parent of ptr is where we attach the second list to the first. Why? because we now run into another leaf and the parent of ptr is an ancestor of that leaf, so it must also be a parent of the second list. (a more rigorous argument is needed here). Repeat until we attached all lists to the first list.

Picture-wise, the tree starts with a linear list, which is the first list, then the second list was attached and the frontier consists of the second list and the common sublist that is the ancestor of both the first and second list. We move the frontier as we attach new lists and update ptr in that frontier.

ZhangBZ replied in the same post with very elegant code.