Binary Tree Construction from Preorder and Inorder Traversal

The goal is to construct a binary tree from given preorder and inorder traversal lists of the tree nodes.

Example:

Input:

preorder = [1, 2, 4, 7, 3]
inorder = [4, 2, 7, 1, 3]

Output:

Level Order Traversal: 1 2 3 4 7 

Explanation:

The binary tree constructed from the provided traversals will have the following structure:

Each level of the tree is presented in the output separated by spaces.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 3000
• 1 <= data <= 104
• Assume all node values are unique.

Note:

If a node is null, it should not appear in the output. The printed sequence corresponds to level order traversal of the constructed tree.

Follow-up:

Try to optimize your solution to work within O(N) time complexity.