Construct Binary Tree from Preorder and Postorder Traversal

Photo by Brandon Green on Unsplash

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 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]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

Constraints:

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• All the values of preorder are unique.
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• All the values of postorder are unique.
• It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Key Observations

Root Identification:

• The first element in preorder is always the root.

Finding Left Subtree:

• The second element in preorder (if available) is the root of the left subtree.
• Locate this value in postorder to determine the boundary of the left subtree.

Recursive Construction:

• Recursively construct the left and right subtrees using index boundaries determined from postorder.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not postorder:  # Edge case: Empty input
            return None
        if len(preorder) == 1:  # Edge case: Single node tree
            return TreeNode(preorder[0])
        
        post_index = {val: idx for idx, val in enumerate(postorder)}  # Map postorder values to indices
        
        def build(pre_left, pre_right, post_left, post_right):
            if pre_left > pre_right or post_left > post_right:
                return None
            
            root = TreeNode(preorder[pre_left])  # Create root node
            if pre_left == pre_right:
                return root  # No children
            
            # Find left subtree size
            left_subtree_root_val = preorder[pre_left + 1]
            mid = post_index[left_subtree_root_val]
            left_size = mid - post_left + 1  
            
            # Recursively construct left and right subtrees
            root.left = build(pre_left + 1, pre_left + left_size, post_left, mid)
            root.right = build(pre_left + left_size + 1, pre_right, mid + 1, post_right - 1)
            
            return root

        return build(0, len(preorder) - 1, 0, len(postorder) - 1)

Explanation of the Code

Step 1: Base Cases

• If preorder or postorder is empty, return None.
• If there’s only one element, return a single-node tree.

Step 2: Use a HashMap for Fast Lookups

• We create a dictionary (post_index) to store the indices of elements in postorder, allowing O(1) lookups.

Step 3: Recursive Tree Construction

• Identify the root from preorder.
• Find the left subtree root from preorder[pre_left + 1].
• Locate this root in postorder to determine the left subtree size.
• Recursively build the left and right subtrees.

Dry Run

Example Input

Preorder:

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

Postorder:

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

Step-by-Step Execution

Step 1: Create a HashMap of Postorder Indices

We first map each element in postorder to its index for quick lookups.

post_index = {4: 0, 5: 1, 2: 2, 6: 3, 7: 4, 3: 5, 1: 6}

Step 2: Start Recursive Construction

We call:

build(0, 6, 0, 6)

• pre_left = 0, pre_right = 6
• post_left = 0, post_right = 6

Root: 1 (from Preorder)

• 1 is the root.

Find Left Subtree

• The next value in preorder is 2 → left subtree root.
• Find 2 in postorder → index = 2.
• Left subtree size = index - post_left + 1 = 2 - 0 + 1 = 3.

We recursively construct:

build(1, 3, 0, 2)

Step 3: Construct Left Subtree of 1 (Root: 2)

• pre_left = 1, pre_right = 3
• post_left = 0, post_right = 2

Root: 2

• The next value in preorder is 4, which is 2's left child.

Find Left Subtree

• Find 4 in postorder → index = 0.
• Left subtree size = index - post_left + 1 = 0 - 0 + 1 = 1.

We recursively construct:

build(2, 2, 0, 0)

Step 4: Construct Left Subtree of 2 (Leaf: 4)

• pre_left = 2, pre_right = 2
• post_left = 0, post_right = 0

Root: 4

• Since pre_left == pre_right, we return TreeNode(4).

Back to 2, we now construct the right subtree.

build(3, 3, 1, 1)

Step 5: Construct Right Subtree of 2 (Leaf: 5)

• pre_left = 3, pre_right = 3
• post_left = 1, post_right = 1

Root: 5

• Since pre_left == pre_right, we return TreeNode(5).

Now, 2 is fully built:

TreeNode(2, left=TreeNode(4), right=TreeNode(5))

Step 6: Construct Right Subtree of 1 (Root: 3)

Back to 1, now we build its right subtree:

build(4, 6, 3, 5)

• pre_left = 4, pre_right = 6
• post_left = 3, post_right = 5

Root: 3

• The next value in preorder is 6 → left subtree root.
• Find 6 in postorder → index = 3.
• Left subtree size = index - post_left + 1 = 3 - 3 + 1 = 1.

We recursively construct:

build(5, 5, 3, 3)

Step 7: Construct Left Subtree of 3 (Leaf: 6)

• pre_left = 5, pre_right = 5
• post_left = 3, post_right = 3

Root: 6

• Since pre_left == pre_right, we return TreeNode(6).

Back to 3, now we build the right subtree:

build(6, 6, 4, 4)

Step 8: Construct Right Subtree of 3 (Leaf: 7)

• pre_left = 6, pre_right = 6
• post_left = 4, post_right = 4

Root: 7

• Since pre_left == pre_right, we return TreeNode(7).

Now, 3 is fully built:

TreeNode(3, left=TreeNode(6), right=TreeNode(7))

Final Reconstructed Tree

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

Time Complexity Analysis

Each node is processed once, and postorder lookups are O(1) due to the hashmap, so the overall complexity is:

• Time Complexity: O(N)
• Space Complexity: O(N) (for recursion stack in the worst case)