LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal

Problem Restatement

We are given two arrays:

The binary tree contains distinct values.

We need to reconstruct and return one possible binary tree. If multiple valid trees exist, returning any one of them is accepted. The problem guarantees that both traversals come from the same binary tree.

Preorder traversal visits nodes in this order:

root, left subtree, right subtree

Postorder traversal visits nodes in this order:

left subtree, right subtree, root

Input and Output

Function shape:

def constructFromPrePost(
    self,
    preorder: list[int],
    postorder: list[int]
) -> Optional[TreeNode]:
    ...

Examples

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]

The tree is:

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

Its preorder traversal is:

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

Its postorder traversal is:

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

Example 2:

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

Output:
[1]

There is only one node, so the answer is a tree with root 1.

First Thought: Use the Traversal Roots

The first element in preorder is always the root.

The last element in postorder is always the root.

So for any subtree:

preorder segment:  [root, ...]
postorder segment: [..., root]

The root value is easy to find.

The hard part is splitting the remaining nodes into the left subtree and right subtree.

Key Insight

After the root in preorder, the next value is the root of one child subtree.

Usually, we treat it as the left subtree root:

preorder[pre_left + 1]

Then we find this value in postorder.

Why does that help?

Postorder lists the entire left subtree before the right subtree. If preorder[pre_left + 1] is the left subtree root, then its position in postorder marks the end of the left subtree.

So if that value appears at index i in postorder, then the left subtree size is:

left_size = i - post_left + 1

Once we know left_size, we can split both traversal arrays into left and right subtree ranges.

Because multiple answers may exist, this convention is valid even when the original tree has only one child at some node.

Algorithm

Build a hash map:

post_index[value] = index in postorder

This lets us find subtree boundaries in O(1) time.

Define a recursive function:

build(pre_left, pre_right, post_left, post_right)

It constructs the tree represented by:

preorder[pre_left : pre_right + 1]
postorder[post_left : post_right + 1]

Steps:

1. If the range is empty, return None.
2. Create the root from preorder[pre_left].
3. If the range has one node, return the root.
4. Let left_root = preorder[pre_left + 1].
5. Find left_root in postorder.
6. Compute the left subtree size.
7. Recursively build the left subtree.
8. Recursively build the right subtree.
9. Return the root.

Walkthrough

Use:

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

The root is:

1

The next preorder value is:

2

So we treat 2 as the left subtree root.

In postorder:

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

value 2 is at index 2.

So the left subtree has:

2 - 0 + 1 = 3

nodes.

Split:

Now recursively build each side.

For left subtree:

preorder  = [2,4,5]
postorder = [4,5,2]

Root is 2.

Next preorder value is 4.

In postorder, 4 ends the left subtree, so left child is 4 and right child is 5.

For right subtree:

preorder  = [3,6,7]
postorder = [6,7,3]

Root is 3.

Left child is 6, right child is 7.

The final tree is:

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

Correctness

For any non-empty subtree, preorder visits the root first. Therefore, preorder[pre_left] is the correct root for the current subtree.

If the subtree has one node, the algorithm returns that node, which is correct.

For a larger subtree, the value preorder[pre_left + 1] is the root of the first child subtree visited by preorder. The algorithm treats that first child subtree as the left subtree. Since the problem allows any valid answer when multiple trees exist, this choice is acceptable.

In postorder, all nodes of a subtree appear contiguously, and the root of that subtree appears last within that block. Therefore, finding preorder[pre_left + 1] in the current postorder range gives the end of that child subtree. This determines exactly how many nodes belong to that subtree.

Using this size, the algorithm splits both preorder and postorder ranges into matching subtree ranges. The recursive calls build valid left and right subtrees from those ranges.

By induction on subtree size, every recursive call returns a tree whose traversals match the given preorder and postorder segments. Therefore, the initial call returns a tree whose preorder and postorder traversals match the input arrays.

Complexity

Let:

n = len(preorder)

Implementation

# 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]:
        post_index = {}

        for i, value in enumerate(postorder):
            post_index[value] = i

        def build(pre_left, pre_right, post_left, post_right):
            if pre_left > pre_right:
                return None

            root = TreeNode(preorder[pre_left])

            if pre_left == pre_right:
                return root

            left_root = preorder[pre_left + 1]
            left_root_index = post_index[left_root]
            left_size = left_root_index - post_left + 1

            root.left = build(
                pre_left + 1,
                pre_left + left_size,
                post_left,
                left_root_index
            )

            root.right = build(
                pre_left + left_size + 1,
                pre_right,
                left_root_index + 1,
                post_right - 1
            )

            return root

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

Code Explanation

We first build an index map for postorder:

post_index = {}

for i, value in enumerate(postorder):
    post_index[value] = i

This lets us find a node’s position in postorder quickly.

The recursive function receives four boundaries:

def build(pre_left, pre_right, post_left, post_right):

The root is always the first value in the current preorder range:

root = TreeNode(preorder[pre_left])

If there is only one node, we return it:

if pre_left == pre_right:
    return root

Otherwise, the next preorder value begins the first child subtree:

left_root = preorder[pre_left + 1]

We find where that subtree ends in postorder:

left_root_index = post_index[left_root]

Then compute its size:

left_size = left_root_index - post_left + 1

Using that size, we build the left subtree:

root.left = build(
    pre_left + 1,
    pre_left + left_size,
    post_left,
    left_root_index
)

and the right subtree:

root.right = build(
    pre_left + left_size + 1,
    pre_right,
    left_root_index + 1,
    post_right - 1
)

The post_right - 1 excludes the current root, because the current root is the last value in the current postorder range.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_traversal(root):
    if not root:
        return []

    return (
        [root.val]
        + preorder_traversal(root.left)
        + preorder_traversal(root.right)
    )

def postorder_traversal(root):
    if not root:
        return []

    return (
        postorder_traversal(root.left)
        + postorder_traversal(root.right)
        + [root.val]
    )

def run_tests():
    s = Solution()

    preorder = [1, 2, 4, 5, 3, 6, 7]
    postorder = [4, 5, 2, 6, 7, 3, 1]
    root = s.constructFromPrePost(preorder, postorder)
    assert preorder_traversal(root) == preorder
    assert postorder_traversal(root) == postorder

    preorder = [1]
    postorder = [1]
    root = s.constructFromPrePost(preorder, postorder)
    assert preorder_traversal(root) == preorder
    assert postorder_traversal(root) == postorder

    preorder = [1, 2]
    postorder = [2, 1]
    root = s.constructFromPrePost(preorder, postorder)
    assert preorder_traversal(root) == preorder
    assert postorder_traversal(root) == postorder

    print("all tests passed")

run_tests()

Test meaning: