Construct Binary Tree from Preorder and Postorder Traversal

Problem Statement

You are given two arrays representing the preorder and postorder traversals of a binary tree with unique values. Your task is to reconstruct the binary tree from these traversals and return its root.

• Preorder Traversal: Visit the root first, then the left subtree, and finally the right subtree.
• Postorder Traversal: Visit the left subtree first, then the right subtree, and finally the root.

If multiple valid trees exist, you can return any one of them.

Task

Implement a function that reconstructs the binary tree given:

• preorder: an array of integers representing the preorder traversal.
• postorder: an array of integers representing the postorder traversal.

Test Cases

Test Case 1

Input:

  "preorder": [1, 2, 4, 5, 3, 6, 7],
  "postorder": [4, 5, 2, 6, 7, 3, 1]

Output:

[1,2,3,4,5,6,7]

Test Case 2

Input:

  "preorder": [10, 20, 40, 50, 30, 60],
  "postorder": [40, 50, 20, 60, 30, 10]

OUTPUT:

[10,20,30,40,50,60]

Constraints

• The number of nodes is between 1 and 30.
• All values in preorder are unique.
• postorder is a permutation of preorder and represents the postorder traversal of the same tree.

Approach

1. Identify the Root:
   • The first element in preorder is the root of the tree.
   • The last element in postorder is also the root.
2. Divide and Conquer:
   • Use the next element in preorder (after the root) to determine the boundary of the left subtree in postorder.
   • Recursively construct the left subtree using the corresponding segments from both arrays.
   • Similarly, construct the right subtree with the remaining segments.
3. Construct the Tree:
   • Combine the results from the recursive calls to form the entire binary tree.
   • Return the root of the constructed tree.