Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogle

Construct Tree from Inorder and Postorder

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2)O(n^2)Yes (deep recursion)YesMention only - never code due to inefficiency
2. Optimized Recursion with Hash MapO(n)O(n)Yes (deep recursion)YesCode this approach in interviews
3. Iterative Stack-BasedO(n)O(n)NoYesMention 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/5)
1. Consider the following code implementing the optimal House Robber III solution. Given the tree: 3 / \ 2 3 \ \ 3 1 What is the value of rob_current when dfs is called on the root node (value 3)?
easy
A. 7
B. 6
C. 8
D. 9

Solution

  1. Step 1: Trace dfs on left child (value 2)

    dfs(2) calls dfs(null) and dfs(3). dfs(null) returns (0,0). dfs(3) returns (3,0) because it has no children. So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(0,0)=0. dfs(3) returns (3,0). For node 2: rob_current=2+0+0=2, not_rob_current=max(0,3)+max(0,0)=3. dfs(2) returns (2,3).
  2. Step 2: Trace dfs on right child (value 3)

    dfs(3) calls dfs(null) and dfs(1). dfs(1) returns (1,0). So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(1,0)=1. dfs(3) returns (3,1).
  3. Step 3: Calculate rob_current at root (value 3)

    rob_current = 3 + left[1] + right[1] = 3 + 3 + 1 = 7.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Sum matches known example output 7 [OK]
Hint: Add node.val + not_rob of children for rob_current [OK]
Common Mistakes:
  • Mixing rob and not_rob values for children
  • Off-by-one in recursion returns
2. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?
easy
A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.
B. Use dynamic programming to store sums of subtrees and combine results bottom-up.
C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.
D. Use a greedy approach to prune paths that exceed the target sum early.

Solution

  1. Step 1: Understand problem constraints and path definition

    The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.
  2. Step 2: Recognize prefix sum with DFS pattern

    Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Prefix sum + DFS solves in linear time [OK]
Hint: Prefix sums track cumulative sums efficiently [OK]
Common Mistakes:
  • Assuming paths must start at root or leaf
  • Using brute force DFS from every node without pruning
  • Trying greedy pruning which fails on negative values
3. What is the time complexity of the iterative postorder traversal using one stack and a pointer on a binary tree with n nodes?
medium
A. O(n log n) due to repeated stack operations
B. O(n) but with O(h) auxiliary space where h is tree height
C. O(n^2) because of nested while loops
D. O(n) because each node is visited and processed once

Solution

  1. Step 1: Analyze node visits

    Each node is pushed and popped exactly once, so operations proportional to n.
  2. Step 2: Confirm no nested repeated work

    Inner loops traverse down left children, but total iterations over all nodes sum to n.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Linear time complexity matches traversal of all nodes once [OK]
Hint: Each node processed once -> O(n) time [OK]
Common Mistakes:
  • Assuming nested loops multiply to n^2
  • Confusing auxiliary space with time
4. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?
hard
A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.
B. Use the brute force approach checking all paths from every node without prefix sums.
C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.
D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

  1. Step 1: Understand path direction relaxation

    Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.
  2. Step 2: Model tree as undirected graph and run DFS from every node

    To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Undirected DFS from every node with prefix sums counts all connected paths [OK]
Hint: Undirected graph DFS needed for arbitrary path directions [OK]
Common Mistakes:
  • Trying to reuse one-directional prefix sum DFS without modification
  • Assuming running DFS twice covers all paths
  • Trying to store both directions in one prefix sum map
5. Suppose the problem is extended: the tree nodes can have duplicate values, and you want to check if the tree is symmetric ignoring node values, only structure matters. Which modification to the original DFS approach correctly solves this variant?
hard
A. Keep the value comparison but add a hash map to track visited nodes to avoid duplicates.
B. Use BFS level-order traversal and check if each level forms a palindrome of node values.
C. Modify the base case to return true if both nodes are null, and skip the value comparison step entirely.
D. Perform a preorder traversal and compare the traversal list with its reverse.

Solution

  1. Step 1: Understand the variant ignores node values, only structure matters

    Therefore, the value comparison step must be removed to avoid false negatives due to duplicates.
  2. Step 2: Modify the DFS to only check if both nodes exist or are null, recursively comparing mirrored subtrees

    Return true if both nodes are null; otherwise, recurse on mirrored children without comparing values.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Ignoring values means skipping value checks but preserving mirrored structure checks [OK]
Hint: Ignore values, check only mirrored structure recursively [OK]
Common Mistakes:
  • Keeping value checks causing false negatives
  • Using BFS palindrome checks which fail on structure
  • Using preorder traversal which ignores mirrored structure
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard