Construct Binary Tree from Preorder and Inorder Traversal

You are given two sequences of integers representing the preorder and inorder traversals of a binary tree. Your task is to reconstruct the binary tree from these sequences and then output its level order (breadth-first) traversal.

The preorder traversal lists nodes in the order: root, left subtree, right subtree, while the inorder traversal lists nodes in the order: left subtree, root, right subtree. You can assume that the binary tree does not contain any duplicate elements and that the input always represents a valid binary tree.

After constructing the binary tree, perform a level order traversal and print the node values separated by a single space.

Note: All formulas, if any, are represented in \( \LaTeX \) format. For instance, the number of nodes is given by \( n \).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer \( n \) representing the number of nodes in the tree.
2. The second line contains \( n \) space-separated integers representing the preorder traversal of the tree.
3. The third line contains \( n \) space-separated integers representing the inorder traversal of the tree.

outputFormat

Output a single line to standard output (stdout) containing the level order traversal of the reconstructed tree. The node values should be printed in breadth-first order, separated by a single space.

5
3 9 20 15 7
9 3 15 20 7

3 9 20 15 7