Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogleFacebook

Construct Tree from Preorder and Inorder

Choose your preparation mode4 modes available
🎯
Construct Tree from Preorder and Inorder
mediumTREEAmazonMicrosoftGoogle

Imagine reconstructing a family tree from two lists: one listing ancestors in the order they were discovered, and another listing them in the order they appear in a family photo. How do you rebuild the entire family tree structure?

💡 This problem is about reconstructing a binary tree given two traversal sequences. Beginners often struggle because it requires understanding how preorder and inorder traversals relate to the tree structure and how to use recursion to rebuild the tree step-by-step.
📋
Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

1 ≤ n ≤ 10^5preorder and inorder consist of unique valuespreorder.length == inorder.length
💡
Example
Input"preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]"
OutputReturn the root of the binary tree: 3 / \ 9 20 / \ 15 7

The first element in preorder is the root (3). In inorder, elements left of 3 (9) form the left subtree, elements right of 3 (15,20,7) form the right subtree. Recursively apply the same logic.

  • Single node tree → returns that node
  • Empty preorder and inorder → returns null
  • Tree with only left children → linear left skewed tree
  • Tree with only right children → linear right skewed tree
⚠️
Common Mistakes
Using array slicing in brute force approach

Leads to O(n^2) time and memory overhead, causing TLE on large inputs

✅ Use indices and a hash map to avoid slicing and repeated searches

Not handling base case correctly (empty subtree)

Leads to infinite recursion or null pointer exceptions

✅ Check if start index > end index before recursion

Incorrectly calculating subtree sizes or indices

Results in wrong tree structure or runtime errors

✅ Carefully compute left subtree size from inorder root index

Forgetting to increment preorder index in optimized approach

Causes infinite loops or incorrect tree construction

✅ Increment preorder index immediately after using root value

Using recursion without considering stack overflow for deep trees

Stack overflow runtime error on very skewed trees

✅ Use iterative stack-based approach or increase recursion limit if allowed

🧠
Brute Force (Pure Recursion with Array Slicing)
💡 This approach is the most straightforward and helps beginners understand the core recursive structure of the problem, even though it is inefficient due to repeated array slicing.

Intuition

The first element in preorder is always the root. Find this root in inorder to split left and right subtrees. Recursively build left and right subtrees by slicing arrays accordingly.

Algorithm

  1. If preorder or inorder is empty, return null.
  2. Take the first element of preorder as root value.
  3. Find the root value index in inorder to separate left and right subtrees.
  4. Recursively build left subtree from preorder[1:left_subtree_size+1] and inorder[:root_index].
  5. Recursively build right subtree from preorder[left_subtree_size+1:] and inorder[root_index+1:].
  6. Return the constructed root node.
💡 The main challenge is understanding how preorder and inorder arrays relate and how to split them correctly for recursive calls.
</>
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(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    root_index = inorder.index(root_val)
    root.left = buildTree(preorder[1:1+root_index], inorder[:root_index])
    root.right = buildTree(preorder[1+root_index:], inorder[root_index+1:])
    return root

# Driver code to test
if __name__ == '__main__':
    pre = [3,9,20,15,7]
    ino = [9,3,15,20,7]
    root = buildTree(pre, ino)
    print(root.val)  # Should print 3
Line Notes
if not preorder or not inorder:Base case: if either list is empty, no tree to build
root_val = preorder[0]Preorder's first element is the root of current subtree
root = TreeNode(root_val)Create a new tree node with root value
root_index = inorder.index(root_val)Find root in inorder to split left and right subtrees
root.left = buildTree(preorder[1:1+root_index], inorder[:root_index])Recursively build left subtree from corresponding slices
root.right = buildTree(preorder[1+root_index:], inorder[root_index+1:])Recursively build right subtree from corresponding slices
return rootReturn the constructed root node
import java.util.*;

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

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        int rootVal = preorder[0];
        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(preorder, 1, 1 + rootIndex),
            Arrays.copyOfRange(inorder, 0, rootIndex));
        root.right = buildTree(
            Arrays.copyOfRange(preorder, 1 + rootIndex, preorder.length),
            Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length));
        return root;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] pre = {3,9,20,15,7};
        int[] ino = {9,3,15,20,7};
        TreeNode root = sol.buildTree(pre, ino);
        System.out.println(root.val); // Should print 3
    }
}
Line Notes
if (preorder.length == 0 || inorder.length == 0) return null;Base case: no nodes to build
int rootVal = preorder[0];Root is first element in preorder
TreeNode root = new TreeNode(rootVal);Create root node
for (int i = 0; i < inorder.length; i++)Find root index in inorder to split subtrees
root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + rootIndex), Arrays.copyOfRange(inorder, 0, rootIndex));Slice preorder and inorder for left subtree
root.right = buildTree(Arrays.copyOfRange(preorder, 1 + rootIndex, preorder.length), Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length));Slice preorder and inorder for right subtree
return root;Return constructed root node
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;
        int rootVal = preorder[0];
        TreeNode* root = new TreeNode(rootVal);
        auto it = find(inorder.begin(), inorder.end(), rootVal);
        int rootIndex = distance(inorder.begin(), it);
        vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + rootIndex);
        vector<int> leftIn(inorder.begin(), inorder.begin() + rootIndex);
        vector<int> rightPre(preorder.begin() + 1 + rootIndex, preorder.end());
        vector<int> rightIn(inorder.begin() + rootIndex + 1, inorder.end());
        root->left = buildTree(leftPre, leftIn);
        root->right = buildTree(rightPre, rightIn);
        return root;
    }
};

int main() {
    Solution sol;
    vector<int> pre = {3,9,20,15,7};
    vector<int> ino = {9,3,15,20,7};
    TreeNode* root = sol.buildTree(pre, ino);
    cout << root->val << endl; // Should print 3
    return 0;
}
Line Notes
if (preorder.empty() || inorder.empty()) return nullptr;Base case: no nodes to build
int rootVal = preorder[0];Root is first element in preorder
TreeNode* root = new TreeNode(rootVal);Create root node
auto it = find(inorder.begin(), inorder.end(), rootVal);Find root index in inorder
int rootIndex = distance(inorder.begin(), it);Calculate root index position
vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + rootIndex);Slice preorder for left subtree
vector<int> rightPre(preorder.begin() + 1 + rootIndex, preorder.end());Slice preorder for right subtree
root->left = buildTree(leftPre, leftIn);Recursively build left subtree
root->right = buildTree(rightPre, rightIn);Recursively build right subtree
return root;Return constructed root node
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

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

// Test
const pre = [3,9,20,15,7];
const ino = [9,3,15,20,7];
const root = buildTree(pre, ino);
console.log(root.val); // Should print 3
Line Notes
if (preorder.length === 0 || inorder.length === 0) return null;Base case: no nodes to build
const rootVal = preorder[0];Root is first element in preorder
const root = new TreeNode(rootVal);Create root node
const rootIndex = inorder.indexOf(rootVal);Find root index in inorder
root.left = buildTree(preorder.slice(1, 1 + rootIndex), inorder.slice(0, rootIndex));Recursively build left subtree
root.right = buildTree(preorder.slice(1 + rootIndex), inorder.slice(rootIndex + 1));Recursively build right subtree
return root;Return constructed root node
⏱
Complexity
TimeO(n^2)
SpaceO(n^2)

Each recursive call slices arrays which takes O(n) time, and there are O(n) calls, leading to O(n^2) time. Space is also O(n^2) due to slicing creating new arrays.

💡 For n=20, this means roughly 400 operations, which is inefficient for large n but fine for small inputs.
Interview Verdict: TLE on large inputs / Accepted on small inputs

This approach is easy to understand but inefficient. It helps build intuition but is not suitable for large inputs due to repeated slicing.

🧠
Optimized Recursion with Hash Map for Inorder Indices
💡 This approach improves efficiency by avoiding repeated searches for root indices in inorder using a hash map, reducing time complexity to O(n).

Intuition

Store inorder value to index mappings in a hash map to find root positions in O(1). Use indices instead of slicing arrays to avoid extra space and time overhead.

Algorithm

  1. Build a hash map from inorder values to their indices.
  2. Define a recursive helper with preorder index and inorder start/end indices.
  3. Use preorder index to get root value, find root index in inorder via hash map.
  4. Recursively build left subtree with inorder start to root index - 1.
  5. Recursively build right subtree with root index + 1 to inorder end.
  6. Return the constructed root node.
💡 Passing indices instead of slicing arrays avoids overhead and hash map lookup makes root finding efficient.
</>
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(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    inorder_index_map = {val: idx for idx, val in enumerate(inorder)}
    preorder_index = 0

    def helper(in_left, in_right):
        nonlocal preorder_index
        if in_left > in_right:
            return None
        root_val = preorder[preorder_index]
        root = TreeNode(root_val)
        preorder_index += 1
        root_index = inorder_index_map[root_val]
        root.left = helper(in_left, root_index - 1)
        root.right = helper(root_index + 1, in_right)
        return root

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

# Driver code
if __name__ == '__main__':
    pre = [3,9,20,15,7]
    ino = [9,3,15,20,7]
    root = buildTree(pre, ino)
    print(root.val)  # Should print 3
Line Notes
inorder_index_map = {val: idx for idx, val in enumerate(inorder)}Precompute inorder indices for O(1) root lookup
preorder_index = 0Global pointer to track current root in preorder
def helper(in_left, in_right):Recursive helper to build subtree within inorder boundaries
if in_left > in_right:Base case: no nodes in this subtree
root_val = preorder[preorder_index]Get current root from preorder
root = TreeNode(root_val)Create root node
preorder_index += 1Move to next root for subsequent calls
root_index = inorder_index_map[root_val]Find root position in inorder quickly
root.left = helper(in_left, root_index - 1)Recursively build left subtree
root.right = helper(root_index + 1, in_right)Recursively build right subtree
return rootReturn constructed root node
import java.util.*;

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

public class Solution {
    private int preorderIndex = 0;
    private Map<Integer, Integer> inorderIndexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        return helper(preorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int inLeft, int inRight) {
        if (inLeft > inRight) return null;
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = inorderIndexMap.get(rootVal);
        root.left = helper(preorder, inLeft, rootIndex - 1);
        root.right = helper(preorder, rootIndex + 1, inRight);
        return root;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] pre = {3,9,20,15,7};
        int[] ino = {9,3,15,20,7};
        TreeNode root = sol.buildTree(pre, ino);
        System.out.println(root.val); // Should print 3
    }
}
Line Notes
private int preorderIndex = 0;Track current root index in preorder
private Map<Integer, Integer> inorderIndexMap = new HashMap<>();Map for O(1) inorder index lookup
for (int i = 0; i < inorder.length; i++)Build map from inorder values to indices
if (inLeft > inRight) return null;Base case: no subtree nodes
int rootVal = preorder[preorderIndex++];Get root and increment preorder index
TreeNode root = new TreeNode(rootVal);Create root node
int rootIndex = inorderIndexMap.get(rootVal);Find root position in inorder quickly
root.left = helper(preorder, inLeft, rootIndex - 1);Recursively build left subtree
root.right = helper(preorder, rootIndex + 1, inRight);Recursively build right subtree
return root;Return constructed root node
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

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

class Solution {
    unordered_map<int, int> inorderIndexMap;
    int preorderIndex = 0;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            inorderIndexMap[inorder[i]] = i;
        }
        return helper(preorder, 0, inorder.size() - 1);
    }

    TreeNode* helper(vector<int>& preorder, int inLeft, int inRight) {
        if (inLeft > inRight) return nullptr;
        int rootVal = preorder[preorderIndex++];
        TreeNode* root = new TreeNode(rootVal);
        int rootIndex = inorderIndexMap[rootVal];
        root->left = helper(preorder, inLeft, rootIndex - 1);
        root->right = helper(preorder, rootIndex + 1, inRight);
        return root;
    }
};

int main() {
    Solution sol;
    vector<int> pre = {3,9,20,15,7};
    vector<int> ino = {9,3,15,20,7};
    TreeNode* root = sol.buildTree(pre, ino);
    cout << root->val << endl; // Should print 3
    return 0;
}
Line Notes
unordered_map<int, int> inorderIndexMap;Hash map for quick inorder index lookup
int preorderIndex = 0;Global preorder index pointer
for (int i = 0; i < inorder.size(); i++)Build map from inorder values to indices
if (inLeft > inRight) return nullptr;Base case: no nodes in subtree
int rootVal = preorder[preorderIndex++];Get root and advance preorder index
TreeNode* root = new TreeNode(rootVal);Create root node
int rootIndex = inorderIndexMap[rootVal];Find root index in inorder efficiently
root->left = helper(preorder, inLeft, rootIndex - 1);Recursively build left subtree
root->right = helper(preorder, rootIndex + 1, inRight);Recursively build right subtree
return root;Return constructed root node
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function buildTree(preorder, inorder) {
    const inorderIndexMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderIndexMap.set(inorder[i], i);
    }
    let preorderIndex = 0;

    function helper(inLeft, inRight) {
        if (inLeft > inRight) return null;
        const rootVal = preorder[preorderIndex++];
        const root = new TreeNode(rootVal);
        const rootIndex = inorderIndexMap.get(rootVal);
        root.left = helper(inLeft, rootIndex - 1);
        root.right = helper(rootIndex + 1, inRight);
        return root;
    }

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

// Test
const pre = [3,9,20,15,7];
const ino = [9,3,15,20,7];
const root = buildTree(pre, ino);
console.log(root.val); // Should print 3
Line Notes
const inorderIndexMap = new Map();Create map for O(1) inorder index lookup
for (let i = 0; i < inorder.length; i++)Build map from inorder values to indices
let preorderIndex = 0;Track current root index in preorder
if (inLeft > inRight) return null;Base case: no subtree nodes
const rootVal = preorder[preorderIndex++];Get root and increment preorder index
const root = new TreeNode(rootVal);Create root node
const rootIndex = inorderIndexMap.get(rootVal);Find root position in inorder quickly
root.left = helper(inLeft, rootIndex - 1);Recursively build left subtree
root.right = helper(rootIndex + 1, inRight);Recursively build right subtree
return root;Return constructed root node
⏱
Complexity
TimeO(n)
SpaceO(n)

Each node is processed once, and root lookup is O(1) via hash map. Space is O(n) for recursion stack and hash map.

💡 For n=20, this means about 20 operations, making it efficient for large inputs.
Interview Verdict: Accepted

This is the standard efficient approach for this problem and is expected in interviews.

🧠
Iterative Approach Using Stack
💡 This approach uses a stack to iteratively build the tree, which can be useful to avoid recursion stack overflow in very deep trees.

Intuition

Use preorder to pick roots and a stack to track ancestors. Use inorder to decide when to pop from stack and attach right children.

Algorithm

  1. Initialize stack and set root as first preorder element.
  2. Iterate over preorder starting from second element.
  3. Keep adding left children while top of stack does not match inorder element.
  4. When top of stack matches inorder, pop stack and attach right child.
  5. Repeat until all nodes are processed.
  6. Return root.
💡 This approach simulates recursion with a stack and uses inorder to know when to switch from left to right subtree.
</>
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(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    stack = [root]
    inorder_index = 0
    for val in preorder[1:]:
        node = stack[-1]
        if node.val != inorder[inorder_index]:
            node.left = TreeNode(val)
            stack.append(node.left)
        else:
            while stack and stack[-1].val == inorder[inorder_index]:
                node = stack.pop()
                inorder_index += 1
            node.right = TreeNode(val)
            stack.append(node.right)
    return root

# Driver code
if __name__ == '__main__':
    pre = [3,9,20,15,7]
    ino = [9,3,15,20,7]
    root = buildTree(pre, ino)
    print(root.val)  # Should print 3
Line Notes
if not preorder:Handle empty input
root = TreeNode(preorder[0])Create root from first preorder element
stack = [root]Initialize stack with root to track ancestors
inorder_index = 0Pointer to track current position in inorder
for val in preorder[1:]:Iterate over remaining preorder elements
node = stack[-1]Look at top node in stack
if node.val != inorder[inorder_index]:If top node not matching inorder, add left child
node.left = TreeNode(val)Create left child
stack.append(node.left)Push left child to stack
else:Top node matches inorder, time to add right child
while stack and stack[-1].val == inorder[inorder_index]:Pop stack while top matches inorder
node = stack.pop()Pop node from stack
inorder_index += 1Move inorder pointer forward
node.right = TreeNode(val)Create right child
stack.append(node.right)Push right child to stack
return rootReturn constructed root node
import java.util.*;

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

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int val = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(val);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(val);
                stack.push(node.right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] pre = {3,9,20,15,7};
        int[] ino = {9,3,15,20,7};
        TreeNode root = sol.buildTree(pre, ino);
        System.out.println(root.val); // Should print 3
    }
}
Line Notes
if (preorder.length == 0) return null;Handle empty input
TreeNode root = new TreeNode(preorder[0]);Create root node
Deque<TreeNode> stack = new ArrayDeque<>();Stack to track ancestors
stack.push(root);Push root to stack
int inorderIndex = 0;Pointer to track current inorder position
for (int i = 1; i < preorder.length; i++)Iterate over preorder elements starting from second
TreeNode node = stack.peek();Look at top node in stack
if (node.val != inorder[inorderIndex]) {Add left child if top node not matching inorder
node.left = new TreeNode(val);Create left child
stack.push(node.left);Push left child to stack
} else {Top node matches inorder, add right child
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {Pop stack while top matches inorder
node = stack.pop();Pop node from stack
inorderIndex++;Move inorder pointer forward
node.right = new TreeNode(val);Create right child
stack.push(node.right);Push right child to stack
return root;Return constructed root node
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> stk;
        stk.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.size(); i++) {
            int val = preorder[i];
            TreeNode* node = stk.top();
            if (node->val != inorder[inorderIndex]) {
                node->left = new TreeNode(val);
                stk.push(node->left);
            } else {
                while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
                    node = stk.top();
                    stk.pop();
                    inorderIndex++;
                }
                node->right = new TreeNode(val);
                stk.push(node->right);
            }
        }
        return root;
    }
};

int main() {
    Solution sol;
    vector<int> pre = {3,9,20,15,7};
    vector<int> ino = {9,3,15,20,7};
    TreeNode* root = sol.buildTree(pre, ino);
    cout << root->val << endl; // Should print 3
    return 0;
}
Line Notes
if (preorder.empty()) return nullptr;Handle empty input
TreeNode* root = new TreeNode(preorder[0]);Create root node
stack<TreeNode*> stk;Stack to track ancestors
stk.push(root);Push root to stack
int inorderIndex = 0;Pointer to track current inorder position
for (int i = 1; i < preorder.size(); i++)Iterate over preorder elements starting from second
TreeNode* node = stk.top();Look at top node in stack
if (node->val != inorder[inorderIndex]) {Add left child if top node not matching inorder
node->left = new TreeNode(val);Create left child
stk.push(node->left);Push left child to stack
} else {Top node matches inorder, add right child
while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {Pop stack while top matches inorder
node = stk.top();Get top node
stk.pop();Pop node from stack
inorderIndex++;Move inorder pointer forward
node->right = new TreeNode(val);Create right child
stk.push(node->right);Push right child to stack
return root;Return constructed root node
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function buildTree(preorder, inorder) {
    if (preorder.length === 0) return null;
    const root = new TreeNode(preorder[0]);
    const stack = [root];
    let inorderIndex = 0;
    for (let i = 1; i < preorder.length; i++) {
        let node = stack[stack.length - 1];
        if (node.val !== inorder[inorderIndex]) {
            node.left = new TreeNode(preorder[i]);
            stack.push(node.left);
        } else {
            while (stack.length && stack[stack.length - 1].val === inorder[inorderIndex]) {
                node = stack.pop();
                inorderIndex++;
            }
            node.right = new TreeNode(preorder[i]);
            stack.push(node.right);
        }
    }
    return root;
}

// Test
const pre = [3,9,20,15,7];
const ino = [9,3,15,20,7];
const root = buildTree(pre, ino);
console.log(root.val); // Should print 3
Line Notes
if (preorder.length === 0) return null;Handle empty input
const root = new TreeNode(preorder[0]);Create root node
const stack = [root];Stack to track ancestors
let inorderIndex = 0;Pointer to track current inorder position
for (let i = 1; i < preorder.length; i++)Iterate over preorder elements starting from second
let node = stack[stack.length - 1];Look at top node in stack
if (node.val !== inorder[inorderIndex]) {Add left child if top node not matching inorder
node.left = new TreeNode(preorder[i]);Create left child
stack.push(node.left);Push left child to stack
} else {Top node matches inorder, add right child
while (stack.length && stack[stack.length - 1].val === inorder[inorderIndex]) {Pop stack while top matches inorder
node = stack.pop();Pop node from stack
inorderIndex++;Move inorder pointer forward
node.right = new TreeNode(preorder[i]);Create right child
stack.push(node.right);Push right child to stack
return root;Return constructed root node
⏱
Complexity
TimeO(n)
SpaceO(n)

Each node is pushed and popped at most once from the stack, so time is O(n). Space is O(n) for stack and tree.

💡 For n=20, this means about 20 operations, efficient and avoids recursion stack issues.
Interview Verdict: Accepted

This approach is less common but useful when recursion depth is a concern.

📊
All Approaches - One-Glance Tradeoffs
💡 The optimized recursive approach with hash map is the best choice for most interviews due to its clarity and efficiency.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2)O(n^2)Yes (deep recursion)YesMention only - never code
2. Optimized Recursion with Hash MapO(n)O(n)Yes (deep recursion)YesCode this approach
3. Iterative Stack-BasedO(n)O(n)NoYesMention or code if recursion depth is a concern
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before interviews. Start by clarifying inputs and outputs, then explain the brute force approach to show understanding. Progress to optimized solutions and discuss tradeoffs.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force recursive approach using array slicing.Discuss inefficiencies and introduce the hash map optimization.Optionally mention the iterative stack approach if recursion depth is a concern.Write clean, tested code for the optimized recursive approach.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of tree traversals, recursion, and optimization techniques. They also check for correctness, efficiency, and handling of edge cases.

Common Follow-ups

  • What if duplicates are allowed? → Use additional data structures or indices to handle duplicates.
  • Can you build the tree from inorder and postorder? → Similar logic but root is last in postorder.
💡 These follow-ups test your adaptability and deeper understanding of tree construction variations.
🔍
Pattern Recognition

When to Use

1. Given preorder and inorder traversals 2. Need to reconstruct original tree 3. Unique node values 4. Use divide and conquer or recursion

Signature Phrases

Given preorder and inorder traversalConstruct binary tree from traversals

NOT This Pattern When

Problems that only require traversal or searching without reconstruction

Similar Problems

Construct Binary Tree from Inorder and Postorder - similar logic but root is last in postorderSerialize and Deserialize Binary Tree - related to tree reconstructionValidate Binary Search Tree - uses inorder traversal properties

Practice

(1/5)
1. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?
medium
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(n h) where h is tree height

Solution

  1. Step 1: Analyze height computation calls

    Height is computed recursively for each node, and each height call traverses subtree nodes.
  2. Step 2: Calculate total calls

    For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Repeated height calls cause quadratic time [OK]
Hint: Repeated height calls cause O(n²) time [OK]
Common Mistakes:
  • Assuming height calls are O(1) leading to O(n) time
  • Confusing height with depth or tree height h
  • Thinking O(n log n) due to balanced tree assumption
2. The following code attempts to flatten a binary tree to a linked list in-place. Identify the bug that causes the flattened list to still have left child pointers, violating the problem requirements.
medium
A. Missing line to set root.left = None
B. Line: flatten(root.left)
C. Line: root.right = prev
D. Line: flatten(root.right)

Solution

  1. Step 1: Review rewiring steps

    The code sets root.right = prev but does not set root.left = None, so left pointers remain.
  2. Step 2: Identify missing step

    Setting root.left = None is required to ensure the flattened list has no left children.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Left pointers must be nullified to meet problem constraints [OK]
Hint: Always set root.left = None when flattening [OK]
Common Mistakes:
  • Forgetting to nullify left pointers
  • Misordering recursive calls causing wrong sequence
  • Losing subtree references by incorrect rewiring
3. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?
medium
A. O(n^2) due to checking grandchildren nodes explicitly
B. O(n) but with extra O(n) space for memoization arrays
C. O(n) because each node is visited once in DFS
D. O(n log n) because of recursive calls and combining results

Solution

  1. Step 1: Identify DFS traversal cost

    The algorithm visits each node exactly once in a postorder DFS traversal.
  2. Step 2: Analyze operations per node

    At each node, constant time operations are done: combining left and right child results, no repeated work.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Linear traversal of n nodes -> O(n) time [OK]
Hint: DFS visits each node once, no repeated subproblems [OK]
Common Mistakes:
  • Assuming O(n^2) due to grandchildren checks
  • Confusing recursion stack space with time complexity
4. What is the space complexity of the optimized recursive DFS approach for checking if a binary tree is symmetric, assuming the tree has n nodes and height h?
medium
A. O(h) due to recursion stack depth proportional to tree height
B. O(1) since no extra space besides variables is used
C. O(n) because all nodes are stored in an auxiliary data structure
D. O(n) due to storing all nodes in a queue for BFS

Solution

  1. Step 1: Identify recursion stack usage

    The recursive calls go as deep as the height of the tree, so the recursion stack uses O(h) space.
  2. Step 2: Confirm no additional data structures store all nodes

    The algorithm does not use queues or arrays to store nodes; it only uses call stack and local variables.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Recursion stack space depends on tree height, not total nodes [OK]
Hint: Recursion stack space = tree height, not total nodes [OK]
Common Mistakes:
  • Confusing BFS queue space with DFS recursion stack
  • Assuming O(n) space due to node storage
  • Ignoring recursion stack space
5. Suppose the problem is modified so that you can rob the same node multiple times (i.e., nodes can be reused any number of times), but still cannot rob directly connected nodes simultaneously. Which modification to the algorithm is necessary to correctly solve this variant?
hard
A. Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse.
B. Use the same DFS with two-value return; no changes needed since adjacency constraints remain.
C. Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection.
D. Modify the DFS to allow revisiting nodes multiple times and use memoization keyed by node and robbing state.

Solution

  1. Step 1: Understand the reuse constraint

    Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.
  2. Step 2: Identify necessary algorithmic change

    We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.
  3. Step 3: Why other options fail

    Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Memoization with extended state handles reuse and adjacency constraints [OK]
Hint: Reuse requires stateful memoization, not simple DFS [OK]
Common Mistakes:
  • Assuming original DFS suffices for reuse
  • Ignoring adjacency constraints when reusing nodes
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