LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal

Problem Restatement

We are given two integer arrays:

inorder
postorder

Both arrays describe the same binary tree.

inorder is the inorder traversal of the tree.

postorder is the postorder traversal of the same tree.

We need to construct and return the original binary tree. The values are unique, and both arrays are guaranteed to describe the same tree. The official constraints also say each value in postorder appears in inorder.

The traversal rules are:

inorder:   left -> root -> right
postorder: left -> right -> root

Input and Output

Item	Meaning
Input	Two integer arrays, `inorder` and `postorder`
Output	The root of the constructed binary tree
Inorder meaning	Left subtree, then root, then right subtree
Postorder meaning	Left subtree, then right subtree, then root
Important condition	Node values are unique

LeetCode gives the TreeNode class:

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

The function shape is:

class Solution:
    def buildTree(self, inorder: list[int], postorder: list[int]) -> Optional[TreeNode]:
        ...

Examples

Consider:

inorder   = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]

The last value in postorder is always the root:

Now find 3 in inorder:

[9] 3 [15, 20, 7]

Everything left of 3 belongs to the left subtree:

[9]

Everything right of 3 belongs to the right subtree:

[15, 20, 7]

So the tree starts like this:

        3
      /   \
     9     ?

Now build the right subtree from:

inorder right part   = [15, 20, 7]
postorder right part = [15, 7, 20]

The last value in that postorder range is 20.

In inorder:

[15] 20 [7]

So 15 is the left child and 7 is the right child.

The final tree is:

First Thought: Use the Traversal Definitions

Postorder gives us the root at the end:

postorder[last] is the root

Inorder tells us how to split the tree:

values before root  -> left subtree
values after root   -> right subtree

So after finding the root, we can recursively build the left and right subtrees.

This is very similar to LeetCode 105, but the root comes from the end of the postorder range instead of the beginning of the preorder range.

Key Insight

For every subtree, the last value in its postorder range is the subtree root.

Once we know the root value, we find its position in inorder.

That position tells us how many nodes belong to the left subtree and how many belong to the right subtree.

For a subtree whose inorder range is:

in_left ... in_right

and whose root appears at:

root_index

the left subtree size is:

left_size = root_index - in_left

The right subtree size is:

right_size = in_right - root_index

To avoid scanning inorder again and again, build a hash map:

value -> index in inorder

Then each root lookup is constant time.

Algorithm

Build a dictionary called in_pos:

in_pos[value] = index

Then define a recursive function:

build(in_left, in_right, post_left, post_right)

This function builds the tree from:

inorder[in_left : in_right + 1]
postorder[post_left : post_right + 1]

For each call:

If the inorder range is empty, return None.
The root value is postorder[post_right].
Create a TreeNode with that value.
Find the root position in inorder using in_pos.
Compute the left subtree size.
Recursively build the left subtree.
Recursively build the right subtree.
Return the root node.

The left subtree ranges are:

inorder:   in_left to root_index - 1
postorder: post_left to post_left + left_size - 1

The right subtree ranges are:

inorder:   root_index + 1 to in_right
postorder: post_left + left_size to post_right - 1

The post_right - 1 endpoint skips the root, because postorder[post_right] has already been used.

Correctness

The last element of a postorder traversal is the root of the current tree. Therefore, each recursive call chooses the correct root for its current subtree.

In inorder traversal, all values before the root belong to the left subtree, and all values after the root belong to the right subtree. Since values are unique, the root has one exact position in the inorder array. This gives one exact split into left and right subtrees.

The algorithm computes the left subtree size from the inorder split. It then uses that size to take exactly the correct number of values from the postorder range for the left subtree. The remaining values before the root in the postorder range belong to the right subtree.

The recursive calls apply the same reasoning to every subtree. When a range becomes empty, the algorithm returns None, which correctly represents a missing child.

Therefore, every node is created once, attached under the correct parent, and placed in the correct left or right subtree. The returned root is the binary tree described by the two traversal arrays.

Complexity

Metric	Value	Why
Time	`O(n)`	Each node is created once, and each inorder index lookup is `O(1)`
Space	`O(n)`	The hash map stores `n` values, and recursion uses stack space

Here, n is the number of nodes.

The recursion stack is O(h), where h is the tree height. In the worst case, h = n.

Implementation

from typing import Optional

# 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 buildTree(self, inorder: list[int], postorder: list[int]) -> Optional[TreeNode]:
        in_pos = {}

        for i, value in enumerate(inorder):
            in_pos[value] = i

        def build(
            in_left: int,
            in_right: int,
            post_left: int,
            post_right: int,
        ) -> Optional[TreeNode]:
            if in_left > in_right:
                return None

            root_value = postorder[post_right]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

            root.left = build(
                in_left,
                root_index - 1,
                post_left,
                post_left + left_size - 1,
            )

            root.right = build(
                root_index + 1,
                in_right,
                post_left + left_size,
                post_right - 1,
            )

            return root

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

Code Explanation

First, we store each value’s position in inorder:

in_pos = {}

for i, value in enumerate(inorder):
    in_pos[value] = i

This makes root lookup fast.

The helper function receives index boundaries:

def build(in_left, in_right, post_left, post_right):

These boundaries describe one subtree.

If the inorder range is empty, there is no node to build:

if in_left > in_right:
    return None

The last value in the current postorder range is the root:

root_value = postorder[post_right]
root = TreeNode(root_value)

Find the root in inorder:

root_index = in_pos[root_value]

Compute the number of nodes in the left subtree:

left_size = root_index - in_left

Build the left subtree:

root.left = build(
    in_left,
    root_index - 1,
    post_left,
    post_left + left_size - 1,
)

Build the right subtree:

root.right = build(
    root_index + 1,
    in_right,
    post_left + left_size,
    post_right - 1,
)

Finally, return the root:

return root

Testing

To test construction, serialize the tree back into inorder and postorder and compare with the original arrays.

from typing import Optional

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

class Solution:
    def buildTree(self, inorder: list[int], postorder: list[int]) -> Optional[TreeNode]:
        in_pos = {}

        for i, value in enumerate(inorder):
            in_pos[value] = i

        def build(
            in_left: int,
            in_right: int,
            post_left: int,
            post_right: int,
        ) -> Optional[TreeNode]:
            if in_left > in_right:
                return None

            root_value = postorder[post_right]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

            root.left = build(
                in_left,
                root_index - 1,
                post_left,
                post_left + left_size - 1,
            )

            root.right = build(
                root_index + 1,
                in_right,
                post_left + left_size,
                post_right - 1,
            )

            return root

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

def inorder_values(root):
    if root is None:
        return []

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

def postorder_values(root):
    if root is None:
        return []

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

def run_tests():
    s = Solution()

    inorder1 = [9, 3, 15, 20, 7]
    postorder1 = [9, 15, 7, 20, 3]
    root1 = s.buildTree(inorder1, postorder1)
    assert inorder_values(root1) == inorder1
    assert postorder_values(root1) == postorder1

    inorder2 = [-1]
    postorder2 = [-1]
    root2 = s.buildTree(inorder2, postorder2)
    assert inorder_values(root2) == inorder2
    assert postorder_values(root2) == postorder2

    inorder3 = [4, 3, 2, 1]
    postorder3 = [4, 3, 2, 1]
    root3 = s.buildTree(inorder3, postorder3)
    assert inorder_values(root3) == inorder3
    assert postorder_values(root3) == postorder3

    inorder4 = [1, 2, 3, 4]
    postorder4 = [4, 3, 2, 1]
    root4 = s.buildTree(inorder4, postorder4)
    assert inorder_values(root4) == inorder4
    assert postorder_values(root4) == postorder4

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[9,3,15,20,7]`, `[9,15,7,20,3]`	Standard mixed tree
Single node	Minimum valid tree
Left-skewed tree	Confirms recursive left ranges
Right-skewed tree	Confirms recursive right ranges