106. Construct Binary Tree from Inorder and Postorder Traversal - Explanation

Problem Link

Description

You are given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [2,1,3,4], postorder = 

Output: [1,2,3,null,null,null,4]

Example 2:

Input: inorder = [1], postorder = [1]

Output: [1]

Constraints:

  • 1 <= postorder.length == inorder.length <= 3000.
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



Intuition

The last element of postorder is always the root. Once we identify the root, we find it in the inorder array. Everything to the left of the root in inorder belongs to the left subtree, and everything to the right belongs to the right subtree. We recursively apply this logic, slicing the arrays accordingly.

Algorithm

  1. If postorder or inorder is empty, return null.
  2. Create the root node using the last element of postorder.
  3. Find the index mid of the root value in inorder.
  4. Recursively build the left subtree using inorder[0:mid] and postorder[0:mid].
  5. Recursively build the right subtree using inorder[mid+1:] and postorder[mid:-1].
  6. Return the root node.
# 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]:
        if not postorder or not inorder:
            return None

        root = TreeNode(postorder[-1])
        mid = inorder.index(postorder[-1])
        root.left = self.buildTree(inorder[:mid], postorder[:mid])
        root.right = self.buildTree(inorder[mid + 1:], postorder[mid:-1])
        return root

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n)

Intuition

The previous approach has O(n) lookup time when finding the root in inorder. By precomputing a hash map that stores each value's index in inorder, we achieve O(1) lookups. We also avoid creating new arrays by using index boundaries instead.

Algorithm

  1. Build a hash map mapping each value in inorder to its index.
  2. Maintain a pointer postIdx starting at the end of postorder.
  3. Define dfs(l, r) that builds the tree for the inorder range [l, r]:
    • If l > r, return null.
    • Pop the current root from postorder (decrement postIdx), create a node.
    • Find the root's index in inorder using the hash map.
    • Build the right subtree first (since we're processing postorder from the end), then the left subtree.
  4. Return the result of dfs(0, n-1).
# 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]:
        inorderIdx = {v: i for i, v in enumerate(inorder)}

        def dfs(l, r):
            if l > r:
                return None

            root = TreeNode(postorder.pop())
            idx = inorderIdx[root.val]
            root.right = dfs(idx + 1, r)
            root.left = dfs(l, idx - 1)
            return root

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

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Depth First Search (Optimal)

Intuition

We can eliminate the hash map by using a boundary-based approach. Instead of explicitly finding the root's position, we pass a "limit" value that tells us when to stop building the current subtree. When we encounter the limit in inorder, we know the current subtree is complete. This approach processes both arrays from right to left.

Algorithm

  1. Initialize pointers postIdx and inIdx both at the last index.
  2. Define dfs(limit) that builds the subtree bounded by limit:
    • If postIdx < 0, return null.
    • If inorder[inIdx] equals limit, decrement inIdx and return null (subtree boundary reached).
    • Create a node with postorder[postIdx], decrement postIdx.
    • Build the right subtree with limit set to the current node's value.
    • Build the left subtree with the original limit.
    • Return the node.
  3. Call dfs with an impossible limit value (like infinity) and return the result.
# 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]:
        postIdx = inIdx = len(postorder) - 1
        def dfs(limit):
            nonlocal postIdx, inIdx
            if postIdx < 0:
                return None
            if inorder[inIdx] == limit:
                inIdx -= 1
                return None

            root = TreeNode(postorder[postIdx])
            postIdx -= 1
            root.right = dfs(root.val)
            root.left = dfs(limit)
            return root
        return dfs(float('inf'))

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n) for recursion stack.

Common Pitfalls

Building Left Subtree Before Right When Using Postorder Index

When processing postorder from right to left, you must build the right subtree before the left subtree. The postorder array is structured as [left, right, root], so when traversing backwards, we encounter right subtree elements first.

# Wrong: Building left before right
root.left = dfs(l, idx - 1)
root.right = dfs(idx + 1, r)  # postIdx is now wrong

# Correct: Build right first
root.right = dfs(idx + 1, r)
root.left = dfs(l, idx - 1)

Off-by-One Errors in Array Slicing

When slicing arrays for recursive calls, it's easy to miscalculate the postorder boundaries. The left subtree has mid elements, so postorder[:mid] is correct for the left subtree, and postorder[mid:-1] (excluding the root) is correct for the right subtree.

# Wrong: Including the root in right subtree
root.right = self.buildTree(inorder[mid + 1:], postorder[mid:])

# Correct: Exclude the root (last element)
root.right = self.buildTree(inorder[mid + 1:], postorder[mid:-1])

Assuming Preorder Logic Works for Postorder

In preorder traversal, the root is at the beginning of the array, but in postorder, the root is at the end. Using postorder[0] instead of postorder[-1] as the root will produce an incorrect tree.