889. Construct Binary Tree from Preorder and Postorder Traversal - Detailed Explanation

Problem Statement

You are given two integer arrays:

• preorder: the preorder traversal of a binary tree (visit root, then left subtree, then right subtree).
• postorder: the postorder traversal of the same binary tree (visit left subtree, then right subtree, then root).

Task: Reconstruct and return the binary tree from these traversals.
Note: The binary tree may not be uniquely determined by these traversals in all cases. You only need to return any binary tree that satisfies the given preorder and postorder traversals.

Example 1

• Input:
  preorder = [1,2,4,5,3,6,7]
postorder = [4,5,2,6,7,3,1]
• Output: A binary tree such as:

         1
       /   \
      2     3
     / \   / \
    4   5 6   7
  

• Explanation:
  • In the preorder traversal, the first element is 1 (the root).
  • The second element, 2, is the root of the left subtree.
  • In postorder, the last element is 1 (the root) and the left subtree’s elements appear before the right subtree’s elements.
  • By locating the left subtree root (2) in the postorder array, we can determine the size of the left subtree and then recursively construct the left and right subtrees.

Example 2

• Input:
  preorder = [1]
postorder = [1]
• Output: A single-node tree with root 1.
• Explanation:
  When there is only one node, both traversals are simply [1].

Constraints

• All values in the arrays are unique.
• The number of nodes in the tree is at least 1.
• It is guaranteed that at least one binary tree exists that satisfies the given traversals.

Hints and Intuition

• Observation 1:
  The first element of the preorder array is always the root of the tree.

• Observation 2:
  The last element of the postorder array is always the root of the tree.

• Key Insight:
  After the root in preorder, the next element is the root of the left subtree. By finding this element in the postorder array, you can determine the boundary (and thus the size) of the left subtree. The remaining elements then belong to the right subtree.

• Recursive Strategy:

  1. Create the root using the first element in preorder.
  2. If there is only one node, return it.
  3. Otherwise, find the left subtree size:
     • Let L be the index of preorder[1] in the postorder array plus one.
  4. Recursively build:
     • The left subtree from preorder[1 : L+1] and postorder[0 : L].
     • The right subtree from the remaining elements.

Detailed Approach: Recursive Construction

Step-by-Step Walkthrough

Consider the example:
preorder = [1,2,4,5,3,6,7] and
postorder = [4,5,2,6,7,3,1].

1. Root Identification:

   • Preorder: The first element is 1 → this is the root.
   • Postorder: The last element is also 1 (confirms the root).

2. Determine Left Subtree:

   • Look at the second element of preorder, which is 2.
   • Find 2 in the postorder array; suppose its index is 2 (0-indexed).
   • The size of the left subtree is index + 1 = 3 (elements [4,5,2] in postorder).
   • Therefore:
     • Left Subtree Preorder: Elements from index 1 to 3 → [2,4,5].
     • Left Subtree Postorder: First 3 elements → [4,5,2].

3. Build Subtrees Recursively:

   • Left Subtree:
     • Preorder: [2,4,5]
     • Postorder: [4,5,2]
   • Right Subtree:
     • Preorder: Remaining elements → [3,6,7]
     • Postorder: Elements after left subtree up to last element (excluding root) → [6,7,3]

4. Repeat Recursively:

   • For each subtree, repeat the process: set the first element of preorder as root, determine left subtree size by locating the next element in postorder, and then build left and right children.

5. Base Case:

   • When there is only one element in the array, create a node and return it.

Code Implementation

Python Implementation