120. Construct a Binary Tree From Inorder and Preorder Traversals, Print Its Postorder

Given the inorder traversal and the preorder traversal of a binary tree with n distinct values (each on its own input line, space-separated), reconstruct the tree and print its postorder traversal, space-separated.

Input: Two lines: the first has n space-separated values of the inorder traversal, the second has n space-separated values of the preorder traversal. Output: Print the postorder traversal of the reconstructed tree, space-separated.

1 <= n <= 10^5, all n values are distinct

This reconstruction relies on all node values being DISTINCT (as this problem's constraints guarantee) - with duplicate values, a single value's position in inorder would be ambiguous, breaking the whole splitting logic.

Given a tree's inorder and preorder traversal sequences, rebuild the original tree, then print its postorder traversal. Brute force: There isn't a meaningfully 'slower but simpler' alternative here beyond the direct recursive reconstruction - the recursive splitting IS the natural and expected approach; the main efficiency concern is how quickly you can find the root's position within inorder at each step. Optimised: Precomputing a hashmap from VALUE to its INDEX in the inorder array (built once upfront) turns each 'find the root's position in inorder' lookup into O(1), instead of an O(n) linear search repeated at every recursive call - this is what keeps the overall reconstruction at O(n) instead of O(n²).

Take the first element of the current preorder segment as the root, scan the current inorder segment linearly to find that value's position (splitting it into left and right parts), then build brand-new copied arrays for the left and right preorder/inorder segments and recurse on those copies to build the left and right subtrees. This correctly reconstructs the tree since it mirrors the recursive definition of preorder/inorder decomposition, but both the linear search for the root's position and the repeated copying of subarrays at every level of recursion add substantial redundant work. Time: O(n^2) Space: O(n^2)

Precompute a hashmap from each value to its index within the inorder array in a single O(n) pass, then reconstruct the tree exactly as in the previous approach using index ranges rather than copies, but find each root's position with an O(1) hashmap lookup instead of a linear scan. This removes the last remaining bottleneck, since every recursive call now does only constant work beyond its two recursive sub-calls, bringing tree construction down to linear time; a final O(n) postorder traversal then prints the reconstructed tree. Time: O(n) Space: O(n)

Keep the same linear scan through the inorder range to find each root's position, but instead of copying subarrays for each recursive call, pass only start/end index bounds into the original preorder and inorder arrays. This still costs the same O(n) search per call as brute force, and hence the same overall O(n^2) time, but it eliminates the O(n^2) space blow-up from repeated array copying, since no new arrays are ever allocated during the recursion. Time: O(n^2) Space: O(n)

1. The FIRST value of preorder is always the current subtree's root. 2. Find that root's position within the inorder sequence - everything to its LEFT in inorder belongs to the left subtree, everything to its RIGHT belongs to the right subtree. 3. Recurse on the corresponding slices of both preorder and inorder for the left subtree, then the right subtree, and finally emit the current root (postorder = left, right, root).

Time: O(n) with the index-lookup hashmap precomputed; O(n²) without it, due to repeated linear searches for the root's position. Space: O(n), for the hashmap and the recursion stack.

Test with n=1 (single node), a fully skewed tree (every node has only one child), and n=10^5 for performance.

Be ready to explain explicitly WHY the hashmap precomputation matters - a very common mistake is searching for the root's position in inorder with a linear scan at every recursive call, silently degrading an O(n) algorithm to O(n²).