LeetCode 106 - Construct Binary Tree from Inorder and Postorder Traversal

LeetCode Problem 106

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Solution

Problem Understanding

The problem provides two traversal orders of the same binary tree:

inorder, which follows the order:

left subtree, root, right subtree

postorder, which follows the order:

left subtree, right subtree, root

We must reconstruct the original binary tree and return its root node.

The key challenge is understanding how these traversals uniquely identify the structure of the tree. Since all values are guaranteed to be unique, every node can be identified unambiguously in both arrays.

For example:

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

The last element of postorder is always the root of the current subtree. Here, 3 is the root.

In the inorder traversal:

[9, 3, 15, 20, 7]
    ^

Everything to the left of 3 belongs to the left subtree, and everything to the right belongs to the right subtree.

That means:

Left subtree inorder: [9]
Right subtree inorder: [15,20,7]

Using the same logic recursively, we can rebuild the entire tree.

The constraints are important:

Up to 3000 nodes means an inefficient repeated scanning solution may become too slow.
Values are unique, which allows us to use a hash map for fast index lookups.
The traversals are guaranteed valid, so we do not need to handle malformed input.

Important edge cases include:

A tree with only one node
Completely skewed trees, where recursion depth becomes large
Trees where one subtree is empty
Large inputs where repeated linear searches would cause time limit issues

Because the traversals are guaranteed correct and values are unique, we can safely reconstruct the tree recursively without ambiguity.

Approaches

Brute Force Approach

A straightforward solution recursively reconstructs the tree by:

Taking the last element of the current postorder segment as the root
Searching linearly through the inorder array to find the root position
Splitting the inorder array into left and right subtree portions
Recursively rebuilding both subtrees

This works because:

Postorder always places the root at the end
Inorder tells us how nodes are divided between left and right subtrees

However, the expensive part is repeatedly scanning the inorder array to find root positions. In the worst case, such as a skewed tree, every recursive call performs an O(n) search.

That leads to overall O(n^2) time complexity.

With up to 3000 nodes, this can become inefficient.

Optimal Approach

The key optimization is to avoid repeatedly searching the inorder array.

Since node values are unique, we can preprocess the inorder traversal into a hash map:

value -> inorder index

This allows every root position lookup to be performed in O(1) time.

The recursive structure remains the same:

The last postorder value is the root
The inorder index splits left and right subtrees
Recursively construct the right subtree first, then the left subtree

Building the right subtree first is important because we consume postorder values from the end backward.

This reduces the overall time complexity to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated linear scans of inorder array
Optimal	O(n)	O(n)	Uses hash map for constant time inorder lookup

Algorithm Walkthrough

Step 1: Build an inorder index map

Create a hash map that stores:

node value -> index in inorder traversal

Example:

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

map = {
    9:0,
    3:1,
    15:2,
    20:3,
    7:4
}

This allows us to instantly determine where a root splits the inorder traversal.

Step 2: Track the current postorder position

The last element in postorder is always the current root.

We maintain a pointer:

postorder_index = len(postorder) - 1

Each time we create a node, we decrement this pointer.

Step 3: Define recursive subtree boundaries

The recursive function operates on a segment of the inorder array:

build(left, right)

Where:

left is the left boundary in inorder
right is the right boundary in inorder

If:

left > right

there are no nodes in this subtree, so return None.

Step 4: Create the current root node

Take:

root_value = postorder[postorder_index]

Create a tree node with this value and decrement the index.

Step 5: Find the root position in inorder

Using the hash map:

inorder_index = inorder_map[root_value]

This divides the inorder segment into:

Left subtree:

left -> inorder_index - 1

Right subtree:

inorder_index + 1 -> right

Step 6: Build the right subtree first

This step is crucial.

Because postorder traversal is:

left -> right -> root

and we are processing from the end backward, the next node belongs to the right subtree first.

So we recursively build:

root.right

before:

root.left

Step 7: Return the constructed subtree

After constructing both children, return the root node.

The recursion naturally rebuilds the entire tree.

Why it works

The algorithm works because inorder and postorder traversals together uniquely determine the structure of a binary tree when node values are unique.

At every recursive step:

Postorder identifies the current root
Inorder determines which nodes belong to the left and right subtrees
Recursive subdivision preserves the exact subtree structure

Processing the right subtree before the left subtree ensures that the postorder pointer always aligns with the correct nodes.

Python Solution

# 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]:
        inorder_index_map = {
            value: index
            for index, value in enumerate(inorder)
        }

        postorder_index = len(postorder) - 1

        def build(left: int, right: int) -> Optional[TreeNode]:
            nonlocal postorder_index

            if left > right:
                return None

            root_value = postorder[postorder_index]
            postorder_index -= 1

            root = TreeNode(root_value)

            inorder_index = inorder_index_map[root_value]

            root.right = build(inorder_index + 1, right)
            root.left = build(left, inorder_index - 1)

            return root

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

The implementation begins by preprocessing the inorder traversal into a hash map. This avoids repeated linear scans and gives constant time access to node positions.

The variable postorder_index tracks the current root node in the postorder traversal. Since postorder ends with the root, we start from the last index and move backward.

The recursive build(left, right) function reconstructs the subtree corresponding to the inorder segment between left and right.

If the boundaries become invalid, meaning left > right, the subtree is empty and the function returns None.

Otherwise, the current root value is taken from postorder[postorder_index]. A new TreeNode is created, and the postorder pointer is decremented.

Using the hash map, we locate the root in the inorder traversal. This splits the subtree into left and right sections.

The algorithm recursively constructs the right subtree first because we are traversing postorder backward. After the right subtree is complete, it constructs the left subtree.

Finally, the root node is returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    inorderIndexMap := make(map[int]int)

    for index, value := range inorder {
        inorderIndexMap[value] = index
    }

    postorderIndex := len(postorder) - 1

    var build func(left int, right int) *TreeNode

    build = func(left int, right int) *TreeNode {
        if left > right {
            return nil
        }

        rootValue := postorder[postorderIndex]
        postorderIndex--

        root := &TreeNode{Val: rootValue}

        inorderIndex := inorderIndexMap[rootValue]

        root.Right = build(inorderIndex+1, right)
        root.Left = build(left, inorderIndex-1)

        return root
    }

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

The Go implementation follows the same recursive logic as the Python version.

A map[int]int stores inorder indices for constant time lookup.

Go uses pointers for tree nodes, so subtree construction returns *TreeNode. Empty subtrees are represented with nil.

The recursive function is defined as a closure so it can access postorderIndex and inorderIndexMap directly without additional parameters.

Since Go slices are references to arrays, no additional copying occurs during recursion, which keeps memory usage efficient.

Worked Examples

Example 1

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

Initial State

Variable	Value
postorderIndex	4
Current Root	3

Root node:

In inorder:

[9, 3, 15, 20, 7]
    ^

Left subtree inorder:

[9]

Right subtree inorder:

[15,20,7]

Build Right Subtree

Next postorder value:

Tree becomes:

    3
     \
      20

Inorder split around 20:

[15, 20, 7]
      ^

Left subtree:

[15]

Right subtree:

[7]

Build Right Child of 20

Next postorder value:

Tree:

No further children exist.

Build Left Child of 20

Next postorder value:

Tree:

Build Left Subtree of 3

Next postorder value:

Final tree:

Example 2

inorder   = [-1]
postorder = [-1]

Only one node exists.

Step	Value
Root	-1
Left Subtree	None
Right Subtree	None

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is processed exactly once
Space	O(n)	Hash map plus recursion stack

The algorithm visits every node once and performs constant time work per node. The inorder index map allows root positions to be found in O(1) time.

The recursion stack can reach O(n) depth in a skewed tree. The hash map also stores all node values, requiring linear space.

Test Cases

from collections import deque

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, postorder):
        inorder_index_map = {
            value: index
            for index, value in enumerate(inorder)
        }

        postorder_index = len(postorder) - 1

        def build(left, right):
            nonlocal postorder_index

            if left > right:
                return None

            root_value = postorder[postorder_index]
            postorder_index -= 1

            root = TreeNode(root_value)

            inorder_index = inorder_index_map[root_value]

            root.right = build(inorder_index + 1, right)
            root.left = build(left, inorder_index - 1)

            return root

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

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

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

solution = Solution()

# Example 1 from problem statement
root = solution.buildTree(
    [9,3,15,20,7],
    [9,15,7,20,3]
)
assert level_order(root) == [3,9,20,None,None,15,7]

# Single node tree
root = solution.buildTree(
    [-1],
    [-1]
)
assert level_order(root) == [-1]

# Left skewed tree
root = solution.buildTree(
    [4,3,2,1],
    [4,3,2,1]
)
assert level_order(root) == [1,2,None,3,None,4]

# Right skewed tree
root = solution.buildTree(
    [1,2,3,4],
    [4,3,2,1]
)
assert level_order(root) == [1,None,2,None,3,None,4]

# Complete binary tree
root = solution.buildTree(
    [4,2,5,1,6,3,7],
    [4,5,2,6,7,3,1]
)
assert level_order(root) == [1,2,3,4,5,6,7]

# Tree with negative values
root = solution.buildTree(
    [-3,-2,-1],
    [-3,-1,-2]
)
assert level_order(root) == [-2,-3,-1]

# Two node tree, left child only
root = solution.buildTree(
    [2,1],
    [2,1]
)
assert level_order(root) == [1,2]

# Two node tree, right child only
root = solution.buildTree(
    [1,2],
    [2,1]
)
assert level_order(root) == [1,None,2]

Test	Why
Balanced example tree	Validates standard recursive reconstruction
Single node	Verifies minimal input handling
Left skewed tree	Tests worst case recursion depth
Right skewed tree	Ensures right subtree ordering works correctly
Complete binary tree	Validates balanced subtree reconstruction
Negative values	Confirms values themselves do not affect logic
Two node left child	Tests empty right subtree handling
Two node right child	Tests empty left subtree handling

Edge Cases

Single Node Tree

A tree containing only one node is the smallest valid input. Recursive implementations sometimes fail here due to incorrect base conditions or index handling.

For example:

inorder = [-1]
postorder = [-1]

The implementation handles this correctly because the recursive function creates the root node, then both recursive subtree calls immediately terminate when left > right.

Completely Skewed Tree

A skewed tree behaves like a linked list and creates the maximum recursion depth.

Example:

In this case, recursion depth becomes O(n). Some implementations incorrectly process subtree order and produce reversed structures.

The solution avoids this issue by always constructing the right subtree before the left subtree while consuming postorder from the end.

Empty Subtrees During Recursion

Many recursive calls eventually reach situations where a subtree does not exist.

Example:

root.left = None

If boundary conditions are incorrect, recursion may continue infinitely or attempt invalid array access.

The implementation safely terminates recursion using:

if left > right:
    return None

This guarantees empty subtree ranges are handled correctly and recursion stops at the proper time.