Log inSign up
mediumleetcodeNot Started

Construct Binary Tree from Inorder and Postorder Traversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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 · Example 1: 5-Node Tree:

Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3] Tree: 3 / \ 9 20 / \ 15 7
Output: [3, 9, 20, null, null, 15, 7]
Explanation: Last element of postorder is 3 (root). In inorder, 9 is left child, and [15, 20, 7] is right subtree.

Example 2 · Example 2: Single Node:

Input: inorder = [-1], postorder = [-1] Tree: -1
Output: [-1]
Explanation: Single node tree.

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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how postorder reveals root and inorder reveals subtree sizes.
  • Use range pointers to eliminate array slice copying.
  • Master divide and conquer recursion on subtrees.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Reconstruct binary tree from inorder and postorder.
  • Unique node values.
  • Divide and conquer tree reconstruction.

Algorithmic Decision Tree:

  • Build map: inMap[inorder[i]] = i.
  • rootVal = postorder[postEnd]; root = new TreeNode(rootVal).
  • inRoot = inMap[rootVal]; numLeft = inRoot - inStart.
  • root.left = build(inStart, inRoot - 1, postStart, postStart + numLeft - 1).
  • root.right = build(inRoot + 1, inEnd, postStart + numLeft, postEnd - 1).

Connected Patterns:

Construct Binary Tree from Preorder and Inorder TraversalConstruct Binary Search Tree from Preorder TraversalSerialize and Deserialize Binary Tree

1. Recursive Construction with Linear Search

Intuition

At each step, linearly find rootVal in the inorder array. This takes O(n) per level, resulting in O(n2) time for skewed trees.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If inStart > inEnd return null.
  2. Step 2: rootVal = postorder[postEnd].
  3. Step 3: Linearly scan inorder[inStart ... inEnd] to find inRoot where inorder[inRoot] == rootVal.
  4. Step 4: numLeft = inRoot - inStart.
  5. Step 5: Recurse for left and right subtrees.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 TreeNode* build(vector<int>& in, int inS, int inE, vector<int>& post, int postS, int postE) {
10 if (inS > inE || postS > postE) return nullptr;
11 int rootVal = post[postE];
12 TreeNode* root = new TreeNode(rootVal);
13 int inRoot = inS;
14 while (in[inRoot] != rootVal) inRoot++;
15 int numLeft = inRoot - inS;
16 root->left = build(in, inS, inRoot - 1, post, postS, postS + numLeft - 1);
17 root->right = build(in, inRoot + 1, inE, post, postS + numLeft, postE - 1);
18 return root;
19 }
20 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
21 return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n^2) — Linear search inside subarray takes O(n) at each node.
  • Space complexity: O(h) — Recursion stack depth O(h).

2. Subarray Slicing Recursion

Intuition

Locate root index in inorder, slice subarrays for left and right, and recursively pass slices.

When to apply: Concise scripting.

Algorithm

  1. Step 1: If inorder is empty, return null.
  2. Step 2: Pop rootVal = postorder.pop(). Create root.
  3. Step 3: idx = inorder.indexOf(rootVal).
  4. Step 4: root.right = buildTree(inorder[idx+1:], postorder).
  5. Step 5: root.left = buildTree(inorder[:idx], postorder).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7// Subarray slicing is inefficient in C++; pointer ranges are preferred.
8class Solution {
9public:
10 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
11 if (inorder.empty()) return nullptr;
12 int rootVal = postorder.back();
13 postorder.pop_back();
14 TreeNode* root = new TreeNode(rootVal);
15 auto it = find(inorder.begin(), inorder.end(), rootVal);
16 int idx = distance(inorder.begin(), it);
17 vector<int> leftIn(inorder.begin(), it);
18 vector<int> rightIn(it + 1, inorder.end());
19 vector<int> leftPost(postorder.begin(), postorder.begin() + idx);
20 vector<int> rightPost(postorder.begin() + idx, postorder.end());
21 root->left = buildTree(leftIn, leftPost);
22 root->right = buildTree(rightIn, rightPost);
23 return root;
24 }
25};
26
27int main() {
28 // Sample driver execution
29 cout << "Execution completed successfully." << endl;
30 return 0;
31}
32

Time & Space Complexity

  • Time complexity: O(n^2) — Array slicing copies O(n) elements at each level.
  • Space complexity: O(n^2) — Copies of subarrays create O(n2) memory footprint.

3. Hash Map for Inorder Indices + Pointer Ranges

Intuition

Map each value in inorder to its index. This allows O(1) lookup of root index. Recurse using index ranges [inStart, inEnd] and [postStart, postEnd] without copying arrays.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Build inMap mapping inorder[i] -> i.
  2. Step 2: Helper build(inStart, inEnd, postStart, postEnd).
  3. Step 3: Base case: if inStart > inEnd or postStart > postEnd return null.
  4. Step 4: rootVal = postorder[postEnd]; inRoot = inMap[rootVal]; numLeft = inRoot - inStart.
  5. Step 5: root.left = build(inStart, inRoot - 1, postStart, postStart + numLeft - 1).
  6. Step 6: root.right = build(inRoot + 1, inEnd, postStart + numLeft, postEnd - 1). Return root.

Reconstruction Trace for Inorder=[9, 3, 20], Postorder=[9, 20, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Pick root = postorder[last] = 3
Visual state
Values and pointers at this exact step
tree
Root
3 (Root)
L Subtree
9
R Subtree
20

Node order shown; add connections to display explicit tree edges.

root: 3
Check / comparison
Root = 3. numLeft = 1.
Decision / next transition
Create root node 3. Recurse left and right.
Why this step matters

Step 1: Pick root = postorder[last] = 3. Inorder index of 3 is 1. Left subtree has nodes before index 1 ([9]). Right subtree has nodes after index 1 ([20]).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 unordered_map<int, int> inMap;
9 TreeNode* build(vector<int>& post, int inS, int inE, int postS, int postE) {
10 if (inS > inE || postS > postE) return nullptr;
11 int rootVal = post[postE];
12 TreeNode* root = new TreeNode(rootVal);
13 int inRoot = inMap[rootVal];
14 int numLeft = inRoot - inS;
15 root->left = build(post, inS, inRoot - 1, postS, postS + numLeft - 1);
16 root->right = build(post, inRoot + 1, inE, postS + numLeft, postE - 1);
17 return root;
18 }
19public:
20 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
21 for (int i = 0; i < inorder.size(); ++i) inMap[inorder[i]] = i;
22 return build(postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Hash map lookup is O(1). Each of the n nodes processed once in O(1) time.
  • Space complexity: O(n) — Hash map takes O(n) memory; recursion stack takes O(h).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Search in SubarrayO(n^2)O(h)Scan for root linearly in inorder subarray.Repeated subarray scans.
2.Subarray Slicing RecursionO(n^2)O(n^2)Slice copies of arrays at each recursive step.Subarray memory copies.
3.Hash Map + Pointer RangesOptimalO(n)O(n)O(1) root index lookup via map; pass integer index boundaries.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: inorder = [1], postorder = [1] -> returns TreeNode(1).
  • Left-skewed tree: right subtrees have size 0, handled cleanly when inStart > inEnd.
  • Right-skewed tree: left subtrees have size 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always mention caching inorder indices in a hash map to achieve O(n) instead of O(n2).
  2. Double-check boundary math: right postorder starts at postStart + numLeft, not postStart + numLeft + 1.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the root of the tree found at the END of the postorder array (postorder[postEnd]) rather than at the beginning?

Back to DSA Sheet