#106

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Construct Binary Tree from Inorder and Postorder Traversal

Reconstruct a binary tree from given inorder and postorder arrays using array scanning and hash lookup to optimize recursive divisions.

array hash table divide and conquer tree binary tree

Problem Statement

Given two integer arrays, inorder and postorder, representing the inorder and postorder traversals of a binary tree, construct the binary tree and return its root node. The tree contains unique values, and each element in postorder exists in inorder, allowing precise reconstruction using array scanning and hash-based index lookup for subtree boundaries.

For example, with inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3], the output tree is [3,9,20,null,null,15,7]. Constraints include array lengths up to 3000 and values in the range [-3000,3000], enforcing efficiency in both time and space when using recursion with hash-assisted splits.

Examples

Example 1

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

Output: [3,9,20,null,null,15,7]

Example details omitted.

Example 2

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

Output: [-1]

Example details omitted.

Constraints

1 <= inorder.length <= 3000
postorder.length == inorder.length
-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.

Solution Approach

Recursive Root Identification and Split

Start by noting that the last element of postorder is the root of the current subtree. Use a hash map to find the root index in inorder, which determines the sizes of left and right subtrees. Recursively apply the same logic to construct left and right children, tracking postorder segments accurately. This avoids scanning inorder repeatedly, converting the naive O(n^2) search into O(n) time overall for locating subtree boundaries.

Index Tracking to Avoid Array Copies

Instead of slicing arrays, maintain start and end indices for both inorder and postorder segments to define the current subtree. This reduces memory usage, keeping space complexity proportional to recursion depth. Each recursive call calculates the left subtree size from inorder indices and offsets postorder pointers accordingly. This pattern ensures no element misalignment occurs between inorder and postorder while constructing the tree efficiently.

Base Cases and Null Assignments

Handle base cases where the start index exceeds the end index for a segment, returning null to terminate a subtree. Ensure recursion halts properly to prevent stack overflow on large trees. Each node is created exactly once using the root value from postorder, with left and right child pointers assigned from recursive returns. This ensures correctness, avoids duplicate nodes, and respects unique value constraints inherent to the problem's pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each node is visited once and hash lookups are O(1), while space complexity is O(h) for recursion stack, where h is tree height. Array scanning without slicing and using hash mapping guarantees linear time and controlled space proportional to tree depth.

What Interviewers Usually Probe

Do you identify the root in postorder before splitting inorder?
Can you track subtree indices without creating new arrays to reduce space usage?
Will you handle null subtrees correctly to avoid misalignments in recursion?

Common Pitfalls or Variants

Common pitfalls

Re-scanning inorder in each recursion leading to O(n^2) time complexity.
Incorrectly calculating left and right subtree sizes causing wrong tree structure.
Not handling base cases for empty subtrees resulting in runtime errors.

Follow-up variants

Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Search Tree from Preorder Traversal
Validate Binary Tree from Inorder and Postorder Traversals

FAQ

How do I handle the root identification in this problem?

Always take the last element in the postorder segment as the root, then locate its index in the inorder array using a hash map to split left and right subtrees efficiently.

Why is a hash map needed for inorder indices?

Without a hash map, finding root positions requires scanning inorder repeatedly, leading to O(n^2) time. Hash lookup reduces it to O(1) per node, maintaining linear time complexity.

Can I slice arrays instead of using index pointers?

While slicing works functionally, it increases space usage and can be slower due to repeated array copies. Index tracking preserves O(h) space where h is the recursion depth.

What should I watch for with empty subtrees?

Ensure base cases return null when start indices exceed end indices; failing to do so can create invalid nodes or runtime errors in recursion.

Does this problem pattern differ from preorder + inorder reconstruction?

Yes, this is specifically array scanning plus hash lookup with postorder determining root, whereas preorder + inorder uses first element as root, affecting index calculations and recursion order.

terminal

Solution

Solution 1: Hash Table + Recursion

The last node in the post-order traversal is the root node. We can find the position of the root node in the in-order traversal, and then recursively construct the left and right subtrees.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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]:
        def dfs(i: int, j: int, n: int) -> Optional[TreeNode]:
            if n <= 0:
                return None
            v = postorder[j + n - 1]
            k = d[v]
            l = dfs(i, j, k - i)
            r = dfs(k + 1, j + k - i, n - k + i - 1)
            return TreeNode(v, l, r)

        d = {v: i for i, v in enumerate(inorder)}
        return dfs(0, 0, len(inorder))

Continue Practicing

#105 construct binary tree from preorder and inorder traversal #889 construct binary tree from preorder and postorder traversal #108 convert sorted array to binary search tree