Construct Binary Tree from Inorder and Postorder Traversal

Given two lists representing the inorder and postorder traversal of a binary tree of integer type with 'N' nodes, construct the binary tree and return its root.

The binary tree contains only unique elements.

Input:

First line contains integer 'T', number of test cases.
For each test case:
- First line contains integer 'N', number of nodes.
- Second line contains 'N' space-separated integers, representing the Postorder traversal.
- Third line contains 'N' space-separated integers, representing the Inorder traversal.

Output:

For each test case, print the level order traversal of the constructed binary tree on a new line.

Example:

IN_ORDER = [9, 3, 15, 20, 7]
POST_ORDER = [9, 15, 7, 20, 3]
The resulting binary tree from the traversals is:

Constraints:

1

Question

Construct Binary Tree from Inorder and Postorder Traversal

Given two lists representing the inorder and postorder traversal of a binary tree of integer type with 'N' nodes, construct the binary tree and return its root.

The binary tree contains only unique elements.

Input:

First line contains integer 'T', number of test cases.
For each test case:
- First line contains integer 'N', number of nodes.
- Second line contains 'N' space-separated integers, representing the Postorder traversal.
- Third line contains 'N' space-separated integers, representing the Inorder traversal.

Output:

For each test case, print the level order traversal of the constructed binary tree on a new line.

Example:

IN_ORDER = [9, 3, 15, 20, 7] 
POST_ORDER = [9, 15, 7, 20, 3] 
The resulting binary tree from the traversals is:

Constraints:

1 <= T <= 10
1 <= N <= 10000
1 <= POST_ORDER[i], IN_ORDER[i] <= 100000

Note:

You do not need to print anything; focus on implementing the function.

Accepted Answer

Construct a binary tree from inorder and postorder traversal lists and return its root.

Create a map to store the indices of elements in the inorder traversal list for quick access during tree construction.
Use the postorder list to determine the root of the tree and recursively build left and right subtrees.
Construct the tree by recursively dividing the inorder list based on the root index in postorder list.
Return the root of the constructed binary tree.
Example: IN_ORDER = [9, 3, 15, 20, 7], POST_ORDER = [9, 15, 7, 20, 3]