What happens if you using linear search for root index in inorder repeatedly?

Leads to TLE on large inputs Fix: Use a hash map to store value to index mappings

What happens if you mixing up indices when splitting postorder array?

Incorrect tree structure or runtime errors Fix: Carefully calculate left subtree size and use it to split postorder correctly

Interview Preptree-dfsmediumAmazonMicrosoftGoogle

Construct Tree from Inorder and Postorder

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

🎯

Construct Tree from Inorder and Postorder

mediumTREEAmazonMicrosoftGoogle

Imagine you have the blueprint of a tree's nodes visited in two different orders, and you want to rebuild the original tree structure exactly as it was.

💡 This problem is about reconstructing a binary tree from two traversal sequences. Beginners often struggle because they don't see how the root node is identified and how the tree splits into subtrees recursively. Think of the root as the last visited node in postorder, and the inorder traversal as a guide to split left and right subtrees.

📋

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.

1 ≤ n ≤ 10^5inorder and postorder consist of unique valuesValues in inorder and postorder are the same and represent a valid binary tree

💡

Example

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

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

Root is 3 (last in postorder). In inorder, left subtree is [9], right subtree is [15,20,7]. Recursively build left and right subtrees.

Single node tree → returns that single node
Empty arrays → returns null (empty tree)
Tree with only left children → linear left skewed tree
Tree with only right children → linear right skewed tree

⚠️

Common Mistakes

Using linear search for root index in inorder repeatedly

Leads to TLE on large inputs

✅ Use a hash map to store value to index mappings

Slicing arrays in recursion causing extra space and time overhead

Slower performance and higher memory usage

✅ Pass indices to recursive helper instead of slicing arrays

Incorrect base case leading to infinite recursion or null pointer exceptions

Runtime errors or stack overflow

✅ Check if start index > end index for inorder or postorder segments

Mixing up indices when splitting postorder array

Incorrect tree structure or runtime errors

✅ Carefully calculate left subtree size and use it to split postorder correctly

Not handling empty input arrays

Null pointer exceptions or incorrect output

✅ Return null if inorder or postorder is empty

🧠

Brute Force (Pure Recursion with Linear Search)

💡 This approach is the foundation: it shows how to reconstruct the tree by directly using the definitions of inorder and postorder traversals, even though it is inefficient. It helps build intuition about how the root splits the tree.

Intuition

The last element in postorder is the root. Find this root in inorder to split left and right subtrees. Recursively build left and right subtrees by slicing arrays.

Algorithm

Identify the root as the last element in postorder array.
Find the root index in inorder array by linear search.
Recursively build left subtree from inorder[0:rootIndex] and postorder[0:rootIndex].
Recursively build right subtree from inorder[rootIndex+1:] and postorder[rootIndex:-1].

💡 The challenge is understanding how the root splits the inorder array and how postorder segments correspond to subtrees.

</>

Code

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    if not inorder or not postorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(root_val)
    root_index = inorder.index(root_val)  # linear search
    root.left = buildTree(inorder[:root_index], postorder[:root_index])
    root.right = buildTree(inorder[root_index+1:], postorder[root_index:-1])
    return root

# Example usage:
# inorder = [9,3,15,20,7]
# postorder = [9,15,7,20,3]
# root = buildTree(inorder, postorder)

Line Notes

if not inorder or not postorder:Base case: if either list is empty, no tree to build

root_val = postorder[-1]Last element in postorder is the root of current subtree

root_index = inorder.index(root_val)Find root position in inorder to split left and right subtrees

root.left = buildTree(inorder[:root_index], postorder[:root_index])Recursively build left subtree from left parts

root.right = buildTree(inorder[root_index+1:], postorder[root_index:-1])Recursively build right subtree from right parts

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) return null;
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }
        root.left = buildTree(Arrays.copyOfRange(inorder, 0, rootIndex), Arrays.copyOfRange(postorder, 0, rootIndex));
        root.right = buildTree(Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length), Arrays.copyOfRange(postorder, rootIndex, postorder.length - 1));
        return root;
    }

    // Example main
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        TreeNode root = sol.buildTree(inorder, postorder);
        System.out.println(root.val); // Should print 3
    }
}

Line Notes

if (inorder.length == 0 || postorder.length == 0) return null;Base case: no nodes to build

int rootVal = postorder[postorder.length - 1];Root is last element in postorder

for (int i = 0; i < inorder.length; i++)Find root index in inorder by linear search

root.left = buildTree(Arrays.copyOfRange(inorder, 0, rootIndex), Arrays.copyOfRange(postorder, 0, rootIndex));Build left subtree recursively

root.right = buildTree(Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length), Arrays.copyOfRange(postorder, rootIndex, postorder.length - 1));

Build right subtree recursively

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.empty() || postorder.empty()) return nullptr;
    int rootVal = postorder.back();
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = 0;
    for (int i = 0; i < inorder.size(); i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }
    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
    vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + rootIndex);
    vector<int> rightPostorder(postorder.begin() + rootIndex, postorder.end() - 1);
    root->left = buildTree(leftInorder, leftPostorder);
    root->right = buildTree(rightInorder, rightPostorder);
    return root;
}

int main() {
    vector<int> inorder = {9,3,15,20,7};
    vector<int> postorder = {9,15,7,20,3};
    TreeNode* root = buildTree(inorder, postorder);
    cout << root->val << endl; // Should print 3
    return 0;
}

Line Notes

if (inorder.empty() || postorder.empty()) return nullptr;Base case: no nodes left to build

int rootVal = postorder.back();Root is last element in postorder traversal

for (int i = 0; i < inorder.size(); i++)Find root index in inorder by linear search

vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);Slice inorder for left subtree

root->left = buildTree(leftInorder, leftPostorder);Recursively build left subtree

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function buildTree(inorder, postorder) {
    if (inorder.length === 0 || postorder.length === 0) return null;
    const rootVal = postorder[postorder.length - 1];
    const root = new TreeNode(rootVal);
    const rootIndex = inorder.indexOf(rootVal);
    root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex));
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex, postorder.length - 1));
    return root;
}

// Example usage:
// const inorder = [9,3,15,20,7];
// const postorder = [9,15,7,20,3];
// const root = buildTree(inorder, postorder);
// console.log(root.val); // 3

Line Notes

if (inorder.length === 0 || postorder.length === 0) return null;Base case: no nodes to construct

const rootVal = postorder[postorder.length - 1];Root is last element in postorder

const rootIndex = inorder.indexOf(rootVal);Find root index in inorder by linear search

root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex));Build left subtree recursively

root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex, postorder.length - 1));Build right subtree recursively

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Each recursive call does a linear search for root in inorder (O(n)) and slices arrays (O(n)) leading to O(n^2) time and space due to copying arrays.

💡 For n=20, this means about 400 operations, which is okay for small inputs but too slow for large trees.

Interview Verdict: TLE on large inputs

This approach is too slow for large inputs but is essential to understand the problem and build towards optimization.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^2)`	`O(n^2)`	Yes (deep recursion)	Yes	Mention only - never code due to inefficiency
2. Optimized Recursion with Hash Map	`O(n)`	`O(n)`	Yes (deep recursion)	Yes	Code this approach in interviews
3. Iterative Stack-Based	`O(n)`	`O(n)`	No	Yes	Mention or code if interviewer requests iterative

Practice

(1/5)

1. You need to place the minimum number of cameras in a binary tree so that every node is monitored. A camera at a node monitors its parent, itself, and its immediate children. Which approach guarantees an optimal solution for this problem?

easy

A. Brute force recursion trying all combinations of camera placements

B. Greedy postorder traversal using explicit states to track coverage and camera placement

C. Top-down dynamic programming with memoization based on node coverage

D. Level order traversal placing cameras on all nodes with uncovered children

2. Consider the following code snippet implementing the parent pointer + ancestor set approach for Lowest Common Ancestor. Given the tree below and nodes p=5 and q=1, what is the final returned node's value? Tree structure: 3 / \ 5 1 / \ \ 6 2 8

def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

easy

A. 3

B. 5

C. 1

D. 2

4. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

5. Consider the following buggy code for checking if a binary tree is symmetric. Which line contains the subtle bug that causes incorrect results for asymmetric trees?

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return True
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

medium

A. Line 5: if t1.val != t2.val: return False

B. Line 3: if not t1 or not t2: return True

C. Line 6: return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

D. Line 8: return isMirror(root.left, root.right) if root else True

Start learning this pattern below

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem constraints

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Trace parent map construction

Step 2: Trace ancestor sets and final return

Final Answer:

Quick Check:

Solution

Step 1: Identify camera placement logic

Step 2: Locate incorrect return

Final Answer:

Quick Check:

Solution

Step 1: Examine condition for traversing right subtree

Step 2: Identify effect of wrong condition

Final Answer:

Quick Check:

Solution

Step 1: Analyze base case for null nodes

Step 2: Identify that returning true when only one node is null causes false positives

Final Answer:

Quick Check: