Recursion and Trees
Rebuilding a tree from its traversals
One traversal tells you the roots. Another tells you where to split.
Key idea
Why one traversal is not enough
A single traversal does not determine a tree. Several different trees produce the same in-order sequence, and several produce the same pre-order sequence.
Two of them together do, and the reason is a division of labor: pre-order tells you which value is the root of each piece, and in-order tells you which values fall on each side of it.
The idea on a search tree first
For a search tree the ordering already supplies the in-order sequence, so a single pre-order traversal is enough. That makes a good place to see the splitting idea without the index bookkeeping.
Why it works
The general version
Without the ordering property you need the in-order sequence to find the split. The recursion is: take the next value from pre-order as the root, find it in the in-order sequence, and everything to its left in that sequence is the left subtree while everything to its right is the right subtree.
Recurse on those two pieces, taking further roots from pre-order as you go. The size of the left piece is what tells you how much of the pre-order sequence belongs to it.
Gotcha
Searching for the root each time is the slow part
Scanning the in-order sequence to locate each root turns an O(n) algorithm into O(n squared). Build a dictionary from value to index once, up front, and every lookup becomes constant.
That optimization assumes values are distinct, which these problems normally promise. If they did not, the traversals would not determine the tree uniquely anyway, so the promise is doing double duty.
Tip
Slices are clear, indexes are faster
The demonstration above passes slices, which copies and makes the whole thing O(n squared) in a second way. It is much easier to read, and for an interview it is a reasonable first version.
The efficient version passes index ranges instead and copies nothing. Write the slice version to establish the recursion, then say you would replace the slices with bounds, which is a change every interviewer will accept without making you do it.
Edge cases
Which pair of traversals works
Pre-order with in-order works. Post-order with in-order works, taking roots from the end. Pre-order with post-order does not determine a binary tree uniquely, which is a genuinely good thing to know and occasionally asked.
In-order is the essential one, because it is the only one of the three that tells you how the values divide into two sides.
Predict the output: reading the split off the second traversal
Preorder visits the root first, so preorder[0] names the root. Finding that value in the inorder list is what splits the remaining nodes into the two subtrees. Type the three lines it prints.
Construct Binary Tree From Preorder And Inorder Traversal
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.