Construct Tree from Inorder and Postorder

🎯

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

1. Identify the root as the last element in postorder array.
2. Find the root index in inorder array by linear search.
3. Recursively build left subtree from inorder[0:rootIndex] and postorder[0:rootIndex].
4. 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.

🧠

Optimized Recursion with Hash Map for Index Lookup

💡 This approach improves the brute force by avoiding repeated linear searches for root index in inorder, using a hash map for O(1) lookups. It also avoids slicing arrays by passing indices, which saves memory and time.

Intuition

Store each value's index in inorder in a hash map. Use indices to avoid slicing arrays, passing start and end indices instead. This reduces time complexity significantly.

Algorithm

1. Build a hash map of value to index from inorder array.
2. Use a recursive helper with parameters for current inorder and postorder subarray indices.
3. Root is postorder[end_post], find root index in inorder using hash map.
4. Recursively build left and right subtrees using updated indices without slicing arrays.

💡 Passing indices instead of slicing arrays avoids extra memory and speeds up recursion.

</>

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]:
    idx_map = {val: idx for idx, val in enumerate(inorder)}

    def helper(in_left, in_right, post_left, post_right):
        if in_left > in_right or post_left > post_right:
            return None
        root_val = postorder[post_right]
        root = TreeNode(root_val)
        root_index = idx_map[root_val]
        left_size = root_index - in_left
        root.left = helper(in_left, root_index - 1, post_left, post_left + left_size - 1)
        root.right = helper(root_index + 1, in_right, post_left + left_size, post_right - 1)
        return root

    return helper(0, len(inorder) - 1, 0, len(postorder) - 1)

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

Line Notes

idx_map = {val: idx for idx, val in enumerate(inorder)}Precompute indices for O(1) root lookup

def helper(in_left, in_right, post_left, post_right):Helper uses indices to avoid slicing

if in_left > in_right or post_left > post_right:Base case: no nodes in this subtree

root_val = postorder[post_right]Root is last element in current postorder segment

root_index = idx_map[root_val]Find root index in inorder using hash map

left_size = root_index - in_leftCalculate size of left subtree to split postorder

root.left = helper(in_left, root_index - 1, post_left, post_left + left_size - 1)Build left subtree recursively

root.right = helper(root_index + 1, in_right, post_left + left_size, post_right - 1)Build right subtree recursively

import java.util.*;

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

public class Solution {
    private Map<Integer, Integer> idxMap;
    private int[] postorder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        idxMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            idxMap.put(inorder[i], i);
        }
        return helper(0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode helper(int inLeft, int inRight, int postLeft, int postRight) {
        if (inLeft > inRight || postLeft > postRight) return null;
        int rootVal = postorder[postRight];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = idxMap.get(rootVal);
        int leftSize = rootIndex - inLeft;
        root.left = helper(inLeft, rootIndex - 1, postLeft, postLeft + leftSize - 1);
        root.right = helper(rootIndex + 1, inRight, postLeft + leftSize, postRight - 1);
        return root;
    }

    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); // 3
    }
}

Line Notes

idxMap = new HashMap<>();Hash map stores inorder indices for O(1) lookup

for (int i = 0; i < inorder.length; i++)Populate hash map with value to index

if (inLeft > inRight || postLeft > postRight) return null;Base case: no nodes in current subtree

int rootVal = postorder[postRight];Root is last element in current postorder segment

int rootIndex = idxMap.get(rootVal);Get root index from hash map

int leftSize = rootIndex - inLeft;Calculate left subtree size to split postorder

root.left = helper(inLeft, rootIndex - 1, postLeft, postLeft + leftSize - 1);Build left subtree recursively

root.right = helper(rootIndex + 1, inRight, postLeft + leftSize, postRight - 1);Build right subtree recursively

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

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

class Solution {
    unordered_map<int, int> idxMap;
    vector<int> postorder;

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->postorder = postorder;
        for (int i = 0; i < inorder.size(); i++) {
            idxMap[inorder[i]] = i;
        }
        return helper(0, inorder.size() - 1, 0, postorder.size() - 1);
    }

private:
    TreeNode* helper(int inLeft, int inRight, int postLeft, int postRight) {
        if (inLeft > inRight || postLeft > postRight) return nullptr;
        int rootVal = postorder[postRight];
        TreeNode* root = new TreeNode(rootVal);
        int rootIndex = idxMap[rootVal];
        int leftSize = rootIndex - inLeft;
        root->left = helper(inLeft, rootIndex - 1, postLeft, postLeft + leftSize - 1);
        root->right = helper(rootIndex + 1, inRight, postLeft + leftSize, postRight - 1);
        return root;
    }
};

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

Line Notes

unordered_map<int, int> idxMap;Hash map for O(1) index lookup in inorder

for (int i = 0; i < inorder.size(); i++)Fill hash map with value to index

if (inLeft > inRight || postLeft > postRight) return nullptr;Base case: no nodes to build

int rootVal = postorder[postRight];Root is last element in current postorder segment

int rootIndex = idxMap[rootVal];Get root index from hash map

int leftSize = rootIndex - inLeft;Calculate left subtree size

root->left = helper(inLeft, rootIndex - 1, postLeft, postLeft + leftSize - 1);Build left subtree recursively

root->right = helper(rootIndex + 1, inRight, postLeft + leftSize, postRight - 1);Build right subtree recursively

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

function buildTree(inorder, postorder) {
    const idxMap = new Map();
    inorder.forEach((val, idx) => idxMap.set(val, idx));

    function helper(inLeft, inRight, postLeft, postRight) {
        if (inLeft > inRight || postLeft > postRight) return null;
        const rootVal = postorder[postRight];
        const root = new TreeNode(rootVal);
        const rootIndex = idxMap.get(rootVal);
        const leftSize = rootIndex - inLeft;
        root.left = helper(inLeft, rootIndex - 1, postLeft, postLeft + leftSize - 1);
        root.right = helper(rootIndex + 1, inRight, postLeft + leftSize, postRight - 1);
        return root;
    }

    return helper(0, inorder.length - 1, 0, postorder.length - 1);
}

// 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

const idxMap = new Map();Map for O(1) index lookup in inorder

inorder.forEach((val, idx) => idxMap.set(val, idx));Populate map with value to index

if (inLeft > inRight || postLeft > postRight) return null;Base case: no nodes in subtree

const rootVal = postorder[postRight];Root is last element in current postorder segment

const rootIndex = idxMap.get(rootVal);Get root index from map

const leftSize = rootIndex - inLeft;Calculate left subtree size

root.left = helper(inLeft, rootIndex - 1, postLeft, postLeft + leftSize - 1);Build left subtree recursively

root.right = helper(rootIndex + 1, inRight, postLeft + leftSize, postRight - 1);Build right subtree recursively

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is processed once. Hash map lookup is O(1). No array slicing reduces overhead.

💡 For n=20, about 20 operations, which is efficient and scalable.

Interview Verdict: Accepted and efficient

This is the standard approach to code in interviews for this problem.

🧠

Iterative Approach Using Stack (Advanced)

💡 This approach reconstructs the tree iteratively using a stack to simulate recursion, which is useful for candidates familiar with iterative tree construction. It avoids recursion overhead and is a good demonstration of stack usage.

Intuition

Traverse postorder from end to start, use a stack to keep track of nodes. Use inorder to decide when to pop from stack and attach right children.

Algorithm

1. Initialize stack and set postorder index to last element (root).
2. Create root node and push to stack.
3. Iterate postorder backwards, create nodes and attach as right or left child based on inorder comparison.
4. Pop from stack when inorder matches stack top, then attach left child.

💡 This approach simulates recursion stack and uses inorder to guide subtree attachment.

</>

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
    stack = []
    root_val = postorder[-1]
    root = TreeNode(root_val)
    stack.append(root)
    inorder_index = len(inorder) - 1
    for i in range(len(postorder) - 2, -1, -1):
        node_val = postorder[i]
        node = TreeNode(node_val)
        top = stack[-1]
        if top.val != inorder[inorder_index]:
            top.right = node
            stack.append(node)
        else:
            while stack and stack[-1].val == inorder[inorder_index]:
                top = stack.pop()
                inorder_index -= 1
            top.left = node
            stack.append(node)
    return root

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

Line Notes

stack = []Stack simulates recursion call stack

root_val = postorder[-1]Root is last element in postorder

root = TreeNode(root_val)Create root node

stack.append(root)Push root to stack

inorder_index = len(inorder) - 1Start from end of inorder to match nodes

for i in range(len(postorder) - 2, -1, -1):Traverse postorder backwards excluding root

node_val = postorder[i]Current node value

node = TreeNode(node_val)Create node for current value

top = stack[-1]Peek top of stack

if top.val != inorder[inorder_index]:If top of stack not matching inorder, attach right child

top.right = nodeAttach right child

stack.append(node)Push new node to stack

else:If top matches inorder, pop to find parent for left child

while stack and stack[-1].val == inorder[inorder_index]:Pop nodes matching inorder to find left child parent

top = stack.pop()Pop from stack

inorder_index -= 1Move inorder index left

top.left = nodeAttach left child after popping

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;
        Deque<TreeNode> stack = new ArrayDeque<>();
        int postIndex = postorder.length - 1;
        int inIndex = inorder.length - 1;
        TreeNode root = new TreeNode(postorder[postIndex--]);
        stack.push(root);
        while (postIndex >= 0) {
            TreeNode node = new TreeNode(postorder[postIndex--]);
            TreeNode top = stack.peek();
            if (top.val != inorder[inIndex]) {
                top.right = node;
                stack.push(node);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inIndex]) {
                    top = stack.pop();
                    inIndex--;
                }
                top.left = node;
                stack.push(node);
            }
        }
        return root;
    }

    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); // 3
    }
}

Line Notes

Deque<TreeNode> stack = new ArrayDeque<>();Stack to simulate recursion

int postIndex = postorder.length - 1;Start from last postorder element (root)

int inIndex = inorder.length - 1;Start from last inorder element

TreeNode root = new TreeNode(postorder[postIndex--]);Create root node and decrement postIndex

stack.push(root);Push root to stack

while (postIndex >= 0)Iterate over remaining postorder elements

TreeNode node = new TreeNode(postorder[postIndex--]);Create node for current postorder value

TreeNode top = stack.peek();Peek top of stack

if (top.val != inorder[inIndex])Attach right child if top not matching inorder

top.right = node;Attach right child

stack.push(node);Push new node to stack

elsePop nodes matching inorder to find left child parent

while (!stack.isEmpty() && stack.peek().val == inorder[inIndex])Pop while top matches inorder

top = stack.pop();Pop from stack

inIndex--;Move inorder index left

top.left = node;Attach left child after popping

#include <iostream>
#include <vector>
#include <stack>
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;
    stack<TreeNode*> st;
    int inIndex = inorder.size() - 1;
    int postIndex = postorder.size() - 1;
    TreeNode* root = new TreeNode(postorder[postIndex--]);
    st.push(root);
    while (postIndex >= 0) {
        TreeNode* node = new TreeNode(postorder[postIndex--]);
        TreeNode* top = st.top();
        if (top->val != inorder[inIndex]) {
            top->right = node;
            st.push(node);
        } else {
            while (!st.empty() && st.top()->val == inorder[inIndex]) {
                top = st.top();
                st.pop();
                inIndex--;
            }
            top->left = node;
            st.push(node);
        }
    }
    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; // 3
    return 0;
}

Line Notes

stack<TreeNode*> st;Stack to simulate recursion

int inIndex = inorder.size() - 1;Start from last inorder element

int postIndex = postorder.size() - 1;Start from last postorder element (root)

TreeNode* root = new TreeNode(postorder[postIndex--]);Create root node and decrement postIndex

st.push(root);Push root to stack

while (postIndex >= 0)Iterate over remaining postorder elements

TreeNode* node = new TreeNode(postorder[postIndex--]);Create node for current postorder value

TreeNode* top = st.top();Peek top of stack

if (top->val != inorder[inIndex])Attach right child if top not matching inorder

top->right = node;Attach right child

st.push(node);Push new node to stack

elsePop nodes matching inorder to find left child parent

while (!st.empty() && st.top()->val == inorder[inIndex])Pop while top matches inorder

top = st.top();Get top node

st.pop();Pop from stack

inIndex--;Move inorder index left

top->left = node;Attach left child after popping

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 stack = [];
    let inorderIndex = inorder.length - 1;
    let postIndex = postorder.length - 1;
    const root = new TreeNode(postorder[postIndex--]);
    stack.push(root);
    while (postIndex >= 0) {
        const node = new TreeNode(postorder[postIndex--]);
        let top = stack[stack.length - 1];
        if (top.val !== inorder[inorderIndex]) {
            top.right = node;
            stack.push(node);
        } else {
            while (stack.length && stack[stack.length - 1].val === inorder[inorderIndex]) {
                top = stack.pop();
                inorderIndex--;
            }
            top.left = node;
            stack.push(node);
        }
    }
    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

const stack = [];Stack simulates recursion

let inorderIndex = inorder.length - 1;Start from last inorder element

let postIndex = postorder.length - 1;Start from last postorder element (root)

const root = new TreeNode(postorder[postIndex--]);Create root node and decrement postIndex

stack.push(root);Push root to stack

while (postIndex >= 0)Iterate over remaining postorder elements

const node = new TreeNode(postorder[postIndex--]);Create node for current postorder value

let top = stack[stack.length - 1];Peek top of stack

if (top.val !== inorder[inorderIndex])Attach right child if top not matching inorder

top.right = node;Attach right child

stack.push(node);Push new node to stack

elsePop nodes matching inorder to find left child parent

while (stack.length && stack[stack.length - 1].val === inorder[inorderIndex])Pop while top matches inorder

top = stack.pop();Pop from stack

inorderIndex--;Move inorder index left

top.left = node;Attach left child after popping

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is pushed and popped once from stack, linear time and space.

💡 For n=20, about 20 stack operations, efficient and avoids recursion overhead.

Interview Verdict: Accepted, useful for iterative coding interviews

This approach is less common but shows mastery of iterative tree construction.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the optimized recursion with hash map in 95% of interviews for best balance of clarity and efficiency.

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

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify input uniqueness and validity of traversals.State the brute force recursive approach to build intuition.Explain the optimization using a hash map to avoid repeated searches.Optionally mention the iterative stack-based approach if asked.Write clean, tested code and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of tree traversals, recursion, optimization with hash maps, and ability to write clean code.

Common Follow-ups

• What if duplicates are allowed? → Cannot use hash map, need alternative approach.
• Can you build tree from preorder and inorder? → Similar approach with different root position.

💡 These follow-ups test your understanding of traversal properties and adaptability.

🔍

Pattern Recognition

When to Use

1) Given two traversal arrays of a binary tree, 2) One traversal ends with root, 3) Need to reconstruct tree, 4) Values are unique

Signature Phrases

'Given inorder and postorder traversal arrays''Construct the binary tree from these traversals'

NOT This Pattern When

Problems that ask for tree traversal outputs or serialization, which do not reconstruct trees.

Similar Problems

Construct Tree from Preorder and Inorder - similar root finding and subtree divisionConstruct Tree from Preorder and Postorder - different traversal combination

Practice

1. What is the time complexity of the optimal greedy postorder traversal solution for the Binary Tree Cameras problem, and why?

medium

A. O(n) because each node is visited once in postorder traversal

B. O(n^2) because each node's state depends on its children's states recursively

C. O(n log n) due to recursive calls and state checks at each node

D. O(h) where h is the height of the tree, since recursion depth equals height

Solution

1. Step 1: Analyze traversal visits

   The algorithm visits each node exactly once in a postorder manner, processing left and right children before the node itself.

2. Step 2: Consider work per node

   Each node's processing is O(1) -- checking children's states and updating counters.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single DFS traversal over n nodes -> O(n) time [OK]

Hint: Each node processed once with constant work [OK]

Common Mistakes:

• Assuming recursive calls multiply work to O(n^2)
• Confusing recursion depth with total work
• Thinking state checks add log n factor

2. What is the time complexity of the parent pointer + ancestor set approach for finding the Lowest Common Ancestor in a binary tree with n nodes and height h?

medium

A. O(h^2) because ancestor set lookups take O(h) each and we do up to h lookups

B. O(n^2) because each node's parent is checked multiple times

C. O(n) to build parent map plus O(h) to find LCA, total O(n)

D. O(n log n) due to sorting ancestors before comparison

Solution

1. Step 1: Identify parent map construction cost

   Building the parent map requires visiting each node once, O(n).

2. Step 2: Analyze ancestor set and LCA search

   Ancestor set insertion and lookup are O(1) average. Traversing up to height h for p and q is O(h). Total is O(n) + O(h) ≈ O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Parent map O(n) + ancestor lookup O(h) = O(n) total [OK]

Hint: Parent map build dominates; ancestor lookup is O(h) [OK]

Common Mistakes:

• Confusing ancestor set lookup as O(h)
• Assuming sorting ancestors needed
• Overestimating repeated parent checks

3. Examine the following buggy iterative DFS code for finding all root-to-leaf paths with a given sum. Which line contains the subtle bug that causes incorrect results?

def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if current_sum == targetSum:
            res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res

medium

A. Line appending left child to stack

B. Line initializing stack with root node and path

C. Line appending right child to stack

D. Line checking if current_sum == targetSum without verifying leaf node

Solution

1. Step 1: Identify condition for adding path to results

   Correct code adds path only if current node is leaf and sum matches.

2. Step 2: Locate bug

   Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing leaf check causes incorrect paths in results [OK]

Hint: Always check leaf node before adding path [OK]

Common Mistakes:

• Adding path before confirming leaf node
• Forgetting to backtrack in recursion

4. What is the time complexity of the optimal iterative DFS solution using a prefix sum hash map for the Path Sum III problem on a binary tree with n nodes?

medium

A. O(n) because each node is visited once and prefix sum operations are O(1) on average

B. O(n log n) because each node's prefix sum is updated and queried in a balanced tree

C. O(n^2) because prefix sums are recalculated for each path starting at every node

D. O(n) but with O(n^2) space due to storing all prefix sums for all paths

Solution

1. Step 1: Identify number of node visits

   Each node is pushed and popped from the stack once, so O(n) visits.

2. Step 2: Analyze prefix sum operations

   Hash map lookups and updates are O(1) average, so total O(n) time.

3. Final Answer:

   Option A -> Option B

4. Quick Check:

   Linear time due to single DFS traversal and constant-time prefix sum ops [OK]

Hint: Prefix sums with hash map yield O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n^2) complexity
• Assuming prefix sums require recomputation for each path
• Overestimating space as O(n^2)

5. Suppose you want to invert a binary tree where nodes can have an arbitrary number of children (not just two). Which modification to the inversion algorithm correctly generalizes the inversion to this n-ary tree?

hard

A. Swap only the first and last child pointers recursively, leaving others unchanged.

B. Use BFS to swap children pairwise at each level without recursion.

C. Recursively invert each child's subtree, then reverse the list of children in-place.

D. Invert only the leftmost and rightmost subtrees recursively, ignoring middle children.

Solution

1. Step 1: Understand inversion for binary tree swaps left and right children

   For n-ary trees, inversion means reversing the order of children after inverting each child's subtree.

2. Step 2: Generalize recursion and reversal

   Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.

3. Step 3: Evaluate other options

   Swapping only first and last or partial BFS swaps do not fully invert the tree structure.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Recursion plus reversing children list generalizes inversion correctly [OK]

Hint: Invert subtrees recursively, then reverse children list for n-ary trees [OK]

Common Mistakes:

• Swapping only some children pairs
• Ignoring recursion on all children
• Using BFS without recursion for full inversion