Construct Tree from Preorder and Inorder

🎯

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.

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
2. Optimized Recursion with Hash Map	O(n)	O(n)	Yes (deep recursion)	Yes	Code this approach
3. Iterative Stack-Based	O(n)	O(n)	No	Yes	Mention 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. Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?

easy

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Initialize variables

   inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).

2. Step 2: First iteration (i=3, node_val=20)

   top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.

3. Step 3: Second iteration (i=2, node_val=7)

   top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.

4. Step 4: Third iteration (i=1, node_val=15)

   top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   inorder_index decremented twice after popping 7 and 20 [OK]

Hint: inorder_index decrements only when popping matching nodes [OK]

Common Mistakes:

• Off-by-one error in inorder_index update
• Confusing when to pop stack
• Misreading top.val vs inorder[inorder_index]

2. Given the following code for inverting a binary tree, what is the value of the left child of the root node after calling invertTree(root) on the tree below? Tree structure before inversion:

    2
   / \
  1   3

easy

A. 3

B. 1

C. 2

D. null

Solution

1. Step 1: Trace recursive calls on root=2

   invertTree called on left child (1) and right child (3), both leaves, so their children are null and return immediately.

2. Step 2: Swap left and right children of root=2

   After recursion, root.left and root.right are swapped: left becomes 3, right becomes 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root's left child after inversion is original right child 3 [OK]

Hint: Swapping children after recursion flips subtree positions [OK]

Common Mistakes:

• Confusing left and right child values after inversion
• Forgetting to swap after recursive calls
• Assuming root value changes

3. Consider the following iterative DFS code for finding all root-to-leaf paths with a given sum. Given the tree below and targetSum = 7, what is the final returned list? Tree structure: 5 / \ 4 8 / / \ 11 13 4 Target sum: 7

def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if not node.left and not node.right:
            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

easy

A. []

B. [[5, 4, 11]]

C. [[5, 4]]

D. [[5, 8, 4]]

Solution

1. Step 1: Trace paths and sums

   Paths: 5->4->11 sum=20, 5->8->13 sum=26, 5->8->4 sum=17; none equals 7.

2. Step 2: Confirm no leaf path sums to 7

   Since no leaf path sums to 7, result list remains empty.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No leaf path sums to 7, so empty list returned [OK]

Hint: Check sums only at leaf nodes [OK]

Common Mistakes:

• Confusing intermediate node sums with leaf sums
• Forgetting to check leaf condition

4. What is the time complexity of the iterative DFS solution for finding all root-to-leaf paths with a given sum in a binary tree with N nodes and maximum path length L?

medium

A. O(N) because each node is visited once

B. O(N^2) because all pairs of nodes are compared during traversal

C. O(N * L) because each node's path is copied when pushed onto the stack

D. O(L) because only the path length affects complexity

Solution

1. Step 1: Identify operations per node

   Each node is visited once, but path copying of length up to L occurs when pushing onto stack.

2. Step 2: Calculate total complexity

   Copying paths of length L for up to N nodes leads to O(N * L) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Path copying dominates, so complexity is O(N * L) [OK]

Hint: Path copying causes O(N * L), not just O(N) [OK]

Common Mistakes:

• Assuming O(N) ignoring path copying
• Confusing with quadratic complexity from unrelated operations

5. 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