Construct Binary Tree from Preorder and Postorder: Recursive Partitioning

You are given two integer arrays, preorder and postorder, representing the preorder and postorder traversals of the same binary tree. All values are unique. Your job is to reconstruct any valid binary tree that matches both traversals and return its root.

This is LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal. Unlike the preorder+inorder or inorder+postorder variants, this combination does not always produce a unique tree. When a node has only one child, you cannot tell whether it belongs on the left or right. The problem accepts any valid answer.

Example: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] produces the tree [1,2,3,4,5,6,7].

Key insight: preorder gives roots, postorder gives subtree boundaries

Here is how the two arrays work together:

1. preorder[0] is always the root of the current subtree.
2. preorder[1] (the next element after the root) is the root of the left subtree.
3. Find that left subtree root in postorder. Its position tells you where the left subtree ends in postorder, because postorder visits all of a subtree's nodes before its root.
4. The number of elements from the start of the current postorder range up to and including that position gives you the left subtree size.
5. Use that size to split both arrays and recurse on left and right halves.

The trick that makes this problem different from the inorder-based variants: you do not have inorder to directly split left from right. Instead, you use preorder[1] as a "probe" to find the left subtree boundary in postorder.

Approach: recursive construction

Build a hash map from postorder values to their indices for O(1) lookups. Then recurse with index bounds into both arrays. At each level, the root comes from preorder, and you determine the split point by looking up preorder[preStart + 1] in the postorder hash map.

def construct_from_pre_post(preorder, postorder):
    post_index = {val: i for i, val in enumerate(postorder)}
    n = len(preorder)

    def build(pre_start, pre_end, post_start, post_end):
        if pre_start > pre_end:
            return None

        root = TreeNode(preorder[pre_start])

        if pre_start == pre_end:
            return root

        left_root_val = preorder[pre_start + 1]
        left_end_in_post = post_index[left_root_val]
        left_size = left_end_in_post - post_start + 1

        root.left = build(
            pre_start + 1, pre_start + left_size,
            post_start, left_end_in_post
        )
        root.right = build(
            pre_start + left_size + 1, pre_end,
            left_end_in_post + 1, post_end - 1
        )

        return root

    return build(0, n - 1, 0, n - 1)

Step-by-step walkthrough

We will use preorder = [1,2,4,5,3,6,7] and postorder = [4,5,2,6,7,3,1] to reconstruct this tree:

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

Each recursive call does the same thing: take the root from preorder, use the next element to find the left subtree boundary in postorder, split both arrays, and recurse. The recursion bottoms out when a partition is empty or contains a single node.

Complexity analysis

Time is O(n). You visit each node exactly once, and the hash map gives O(1) lookups for the split point. No array slicing, no linear scans.

Space is O(n). The hash map stores n entries. The recursion stack goes as deep as the tree height: O(n) in the worst case (a skewed tree) and O(log n) for a balanced tree.

Building blocks

1. Recursive tree construction

The core pattern across all "construct tree from traversals" problems is the same: identify the root from one traversal, use the other traversal (or a combination of both) to determine the split between left and right subtrees, then recurse. Here, preorder identifies the root and postorder provides the boundary.

2. Index lookup with hash map

Without the hash map, finding preorder[1] in postorder takes O(n) per call, giving O(n^2) total. The hash map makes each lookup O(1), bringing total time down to O(n). This is the same optimization you use in the preorder+inorder and inorder+postorder variants.

Edge cases

• Single node: both arrays have one element. The base case pre_start == pre_end creates a leaf and returns immediately.
• Left-only tree: when a node has exactly one child, the algorithm assigns it as the left child. This is valid because the problem says "return any answer."
• Two nodes: preorder = [1,2], postorder = [2,1]. Node 2 becomes the left child of 1. The right subtree is empty.

From understanding to recall

You just walked through the full recursive partitioning process. The algorithm hinges on one insight: preorder[1] is the left subtree root, and finding it in postorder tells you the left subtree size. That single lookup drives the entire split.

The details that trip people up are the index arithmetic. You need four bounds (pre_start, pre_end, post_start, post_end) instead of two. You need to remember that pre_start == pre_end is a special base case, because there is no preorder[pre_start + 1] to look up. And you need to correctly compute left_size as left_end_in_post - post_start + 1.

These details are easy to forget under time pressure. Spaced repetition locks them in. You write the solution from scratch at increasing intervals until the index math becomes automatic. If you have already drilled the preorder+inorder variant, this one becomes a natural extension rather than a new problem from scratch.

Related posts

• Construct Binary Tree from Preorder and Inorder Traversal - Similar reconstruction from two traversals
• Construct Binary Tree from Inorder and Postorder Traversal - The inorder+postorder variant
• Binary Tree Preorder Traversal - Understanding the preorder sequence