Construct Binary Tree from Inorder and Postorder Traversal

Medium · Trees · Explanation and code example

Depth First Search (Optimal)

How it works

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.

Steps

  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.

Complexity

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

Things to watch for

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.

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.

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.

Python code example

from typing import List, 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]:
        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'))

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int postIdx;
    int inIdx;

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        postIdx = postorder.size() - 1;
        inIdx = inorder.size() - 1;

        return dfs(postorder, inorder, numeric_limits<int>::max());
    }

private:
    TreeNode* dfs(vector<int>& postorder, vector<int>& inorder, int limit) {
        if (postIdx < 0) {
            return nullptr;
        }

        if (inorder[inIdx] == limit) {
            inIdx--;
            return nullptr;
        }

        TreeNode* root = new TreeNode(postorder[postIdx--]);
        root->right = dfs(postorder, inorder, root->val);
        root->left = dfs(postorder, inorder, limit);
        return root;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations