From the 1996 UF ACM High School Programming Competition
Tree Surgeon
Gator Tree Surgeons isn't your typical landscaping company. They don't trim
trees they put them together. Also they don't work on typical trees.
Instead the specialize in the very rare \textit{ficus binarius},
(a binary tree to us laypeople). One of the most common jobs for
Gator Tree Surgeons (GTS) is to repair trees that have been damaged in
accidents. To do this GTS uses old records of the tree's structure to
help re-create the correct tree. Here's how they do it.
Problem Statement
There are three common listings of binary trees. These are the
preorder (node-left-right), inorder (left-node-right), and postorder
(left-right-node) traversals. Each of these traversals
represents a simple recursive algorithm for visiting each node of
a binary tree, and (in this case) printing it.
Any binary tree can be uniquely identified by any 2 of these
traversals. Therefore, from knowing the preorder and the inorder you
can reconstruct the tree. The same is true for the inorder and postorder,
or preorder and postorder.
Input will be the inorder and postorder representations of the tree.
These will be strings of characters, with each character representing
a node in the tree.
Notes
Realize that the nodes may not be in alphabetical order. There
are many possible ways of ordering a binary tree, and this
is only one of them.
It is not necesary to show the tree, but it may be helpful to see an
example. The example represents the tree found in figure below.
All node values will be unique. There will be at most 20 nodes.
Examples
Enter the postorder traversal: GDLHIEBMJNKFCA
Enter the inorder traversal : DGBHLEIACJMFKN
The preorder traversal is : ABDGEHLICFJMKN
Grader's Test Data
Enter the postorder traversal: hacilem
Enter the inorder traversal : ihcamle
The preorder traversal is : michael
Enter the postorder traversal: acbfged
Enter the inorder traversal : abcdefg
The preorder traversal is : dbacegf
Enter the postorder traversal: ACfsh96Mu
Enter the inorder traversal : AfCushM96
The preorder traversal is : ufACMhs96
