#36 · Trees

Construct Binary Tree from Preorder and Inorder Traversal

Given the pre-order and in-order traversals of a binary tree with distinct values, rebuild and return the tree.

MediumLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Pre-order and in-order sequences

Pre-order lists a subtree's root FIRST, then its left subtree, then its right subtree. In-order lists the left subtree, then the root, then the right subtree. Knowing the root (from pre-order) and where it sits in in-order tells exactly how many nodes belong to the left and to the right.

Memory layout

Two arrays of the same n distinct values. Distinctness is what makes "the position of the root in in-order" unambiguous.

Operation	Cost
find the root in in-order by search	O(n) per node (O(n²) total)
find the root with a hash map	O(1) per node (O(n) total)

Hash map / pointer technique

A map from value to in-order index replaces the linear search. Even that can be avoided: the in-order pointer itself can mark where each subtree ends (a stop value), or a stack can track unfinished ancestors.

Memory layout

A hash table of n entries, or just two integers and a stack of at most h nodes.

Operation	Cost
build the tree	O(n) time, O(n) or O(h) extra space

Why it fits

One traversal alone is ambiguous, but pre-order fixes every subtree's root and in-order fixes its size, so together they determine the tree uniquely.
Pre-order is consumed strictly left to right: the next unused value is always the root of the next subtree to build, so a single shared index suffices (no slicing).
The only expensive step is locating the root in in-order; a hash map (or the stop-value trick) makes it O(1).

Why alternatives degrade

Only one traversal:: Pre-order or in-order alone corresponds to many different trees (for example a left chain and a right chain share the same in-order).
Slice both arrays at every call:: Copies O(n) elements per node: O(n²) time and memory.
Linear indexOf at every call:: O(n) per node: O(n²) total on a skewed tree.
Duplicates in the input:: With repeated values the root's position in in-order is ambiguous. The problem guarantees distinct values.

Four approaches, from naive to production

1 · beginner

Recursion on array slices

time O(n²)space O(n²)

The first pre-order value is the root. Find it in in-order; the values before it are the left subtree, the values after it the right subtree. Slice both arrays accordingly and recurse.

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

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null;
    int rootVal = preorder[0];
    int mid = 0; while (inorder[mid] != rootVal) mid++;
    TreeNode root = new TreeNode(rootVal);
    root.left = buildTree(Arrays.copyOfRange(preorder, 1, mid + 1), Arrays.copyOfRange(inorder, 0, mid));
    root.right = buildTree(Arrays.copyOfRange(preorder, mid + 1, preorder.length), Arrays.copyOfRange(inorder, mid + 1, inorder.length));
    return root;
}

def build_tree(preorder, inorder):
    if not preorder: return None
    root_val = preorder[0]
    mid = inorder.index(root_val)
    root = TreeNode(root_val)
    root.left = build_tree(preorder[1:mid + 1], inorder[:mid])
    root.right = build_tree(preorder[mid + 1:], inorder[mid + 1:])
    return root

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

Flaws & bottlenecks

indexOf is a linear search at every node: O(n) per call.
slice() copies four sub-arrays per call, so total copying is O(n²) on a skewed tree.
Recursion depth equals the tree height.

Interviewer cross-questions

Why is the root the first element of pre-order?

Say: Pre-order visits the node before either subtree, so the first value of any subtree's pre-order segment is that subtree's root.

Why does the in-order index tell the size of the left subtree?

Say: In in-order, the left subtree appears entirely before the root. So the number of values before the root's position is the size of the left subtree, which tells how to split the pre-order segment too.

Why must values be distinct?

Say: The algorithm finds the root by value in the in-order list. With duplicates there can be several candidate positions, and the tree is no longer uniquely determined.

2 · intermediate

Hash map + index ranges

time O(n)space O(n)

Precompute value → in-order index. Recurse on index windows [lo, hi] of the in-order list and consume pre-order values with a single shared pointer, so nothing is sliced or searched.

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> index;
    for (int i = 0; i < (int)inorder.size(); i++) index[inorder[i]] = i;
    int pre = 0;
    function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        TreeNode* root = new TreeNode(preorder[pre++]);
        int mid = index[root->val];
        root->left = build(lo, mid - 1);
        root->right = build(mid + 1, hi);
        return root;
    };
    return build(0, (int)inorder.size() - 1);
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> index = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) index.put(inorder[i], i);
    int[] pre = {0};
    return build(preorder, index, pre, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, Map<Integer, Integer> index, int[] pre, int lo, int hi) {
    if (lo > hi) return null;
    TreeNode root = new TreeNode(preorder[pre[0]++]);
    int mid = index.get(root.val);
    root.left = build(preorder, index, pre, lo, mid - 1);
    root.right = build(preorder, index, pre, mid + 1, hi);
    return root;
}

def build_tree(preorder, inorder):
    index = {}
    for i, v in enumerate(inorder): index[v] = i
    pre = 0
    def build(lo, hi):
        nonlocal pre
        if lo > hi: return None
        root = TreeNode(preorder[pre])
        pre += 1
        mid = index[root.val]
        root.left = build(lo, mid - 1)
        root.right = build(mid + 1, hi)
        return root
    return build(0, len(inorder) - 1)

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const index = new Map<number, number>();
  inorder.forEach((v, i) => index.set(v, i));
  let pre = 0;
  const build = (lo: number, hi: number): TreeNode | null => {
    if (lo > hi) return null;
    const root = new TreeNode(preorder[pre++]);
    const mid = index.get(root.val)!;
    root.left = build(lo, mid - 1);
    root.right = build(mid + 1, hi);
    return root;
  };
  return build(0, inorder.length - 1);
}

Flaws & bottlenecks

The hash table costs O(n) extra memory.
Recursion depth equals the tree height (O(n) for a chain).
Relies on a shared mutable pointer (pre); the order of the two recursive calls matters.

Interviewer cross-questions

Why must the left subtree be built before the right?

Say: Pre-order consumes the left subtree's values first. The shared pointer pre advances in that order, so building right first would assign values to the wrong subtree.

What are lo and hi?

Say: They are the in-order positions of the current subtree. The root's position mid splits them into [lo, mid − 1] (left) and [mid + 1, hi] (right). An empty window (lo > hi) means no node.

How do you avoid the hash map?

Say: Use the stack-based iterative method, or the stop-value recursion: both track subtree boundaries with the in-order pointer instead of looking positions up.

3 · advanced

Iterative with a stack

time O(n)space O(h)

Scan pre-order once. The new node is the left child of the stack top unless that top has already been reached in in-order; in that case pop until the stack top differs from the in-order pointer and attach the new node as the right child of the last popped node.

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty()) return nullptr;
    TreeNode* root = new TreeNode(preorder[0]);
    vector<TreeNode*> stack = {root};
    int inIdx = 0;
    for (int i = 1; i < (int)preorder.size(); i++) {
        TreeNode* node = stack.back();
        TreeNode* child = new TreeNode(preorder[i]);
        if (node->val != inorder[inIdx]) {
            node->left = child;
        } else {
            while (!stack.empty() && stack.back()->val == inorder[inIdx]) {
                node = stack.back(); stack.pop_back();
                inIdx++;
            }
            node->right = child;
        }
        stack.push_back(child);
    }
    return root;
}

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 inIdx = 0;
    for (int i = 1; i < preorder.length; i++) {
        TreeNode node = stack.peek();
        TreeNode child = new TreeNode(preorder[i]);
        if (node.val != inorder[inIdx]) {
            node.left = child;
        } else {
            while (!stack.isEmpty() && stack.peek().val == inorder[inIdx]) {
                node = stack.pop();
                inIdx++;
            }
            node.right = child;
        }
        stack.push(child);
    }
    return root;
}

def build_tree(preorder, inorder):
    if not preorder: return None
    root = TreeNode(preorder[0])
    stack = [root]
    in_idx = 0
    for i in range(1, len(preorder)):
        node = stack[-1]
        child = TreeNode(preorder[i])
        if node.val != inorder[in_idx]:
            node.left = child
        else:
            while stack and stack[-1].val == inorder[in_idx]:
                node = stack.pop()
                in_idx += 1
            node.right = child
        stack.append(child)
    return root

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

Flaws & bottlenecks

The correctness argument is subtle (what the stack and the in-order pointer mean).
Very easy to get the pop loop condition wrong.
The stack can hold O(n) nodes for a left-leaning tree.

Interviewer cross-questions

What does the stack contain?

Say: The nodes on the current left spine whose right child is not decided yet: ancestors that are still "open".

What does comparing the top with inorder[inIdx] mean?

Say: inorder[inIdx] is the next node that in-order will visit, which is the leftmost unfinished node. If the stack top is that node it has no more left descendants, so the next pre-order node must go to the right of it (or of an ancestor).

Why is it O(n)?

Say: Each node is pushed once and popped at most once, and the in-order pointer only moves forward.

4 · expert

Recursion with a stop value

time O(n)space O(h)

Use two shared pointers and a stop value: a subtree ends when the in-order pointer reaches its stop. Pre-order supplies the next root, and in-order tells when a subtree is empty. No hash table and no array copies.

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int pre = 0;
    int inn = 0;
    function<TreeNode*(long long)> build = [&](long long stop) -> TreeNode* {
        if (pre >= (int)preorder.size()) return nullptr;
        if (inn < (int)inorder.size() && inorder[inn] == stop) {
            inn++;
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[pre++]);
        root->left = build(root->val);
        root->right = build(stop);
        return root;
    };
    return build(LLONG_MIN);
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int[] pos = {0, 0};
    return build(preorder, inorder, pos, Long.MIN_VALUE);
}

private TreeNode build(int[] preorder, int[] inorder, int[] pos, long stop) {
    if (pos[0] >= preorder.length) return null;
    if (pos[1] < inorder.length && inorder[pos[1]] == stop) {
        pos[1]++;
        return null;
    }
    TreeNode root = new TreeNode(preorder[pos[0]++]);
    root.left = build(preorder, inorder, pos, root.val);
    root.right = build(preorder, inorder, pos, stop);
    return root;
}

def build_tree(preorder, inorder):
    pre = 0
    inn = 0
    def build(stop):
        nonlocal pre, inn
        if pre >= len(preorder): return None
        if inn < len(inorder) and inorder[inn] == stop:
            inn += 1
            return None
        root = TreeNode(preorder[pre])
        pre += 1
        root.left = build(root.val)
        root.right = build(stop)
        return root
    return build(None)

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  let pre = 0;
  let inn = 0;
  const build = (stop: number | null): TreeNode | null => {
    if (pre >= preorder.length) return null;
    if (inn < inorder.length && inorder[inn] === stop) {
      inn++;
      return null;
    }
    const root = new TreeNode(preorder[pre++]);
    root.left = build(root.val);
    root.right = build(stop);
    return root;
  };
  return build(null);
}

Flaws & bottlenecks

Elegant but non-obvious: the meaning of stop and of the two pointers is hard to see at first.
Mutable shared state (pre and inn) captured by a closure.
Recursion depth equals the tree height, so a chain still needs O(n) stack.

Interviewer cross-questions

What is the stop value?

Say: The node that comes right AFTER the current subtree in in-order. For a left subtree it is the parent; for a right subtree it is the same stop as the parent's subtree. When inorder[inn] equals it, the current subtree has run out of nodes.

Why consume (inn++) when the stop value is reached?

Say: Reaching the stop means the subtree is empty on this side. The stop node itself will be "visited" in in-order right after, so we move past it to keep the pointer aligned for the sibling subtree.

How does it compare with the hash-map version?

Say: Same O(n) time. It saves the O(n) table and runs on arrays alone, at the price of being harder to explain.

Synchronized code walkthrough

Showing: Recursion on array slices — shares the player above; click any step to jump.

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

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null;
    int rootVal = preorder[0];
    int mid = 0; while (inorder[mid] != rootVal) mid++;
    TreeNode root = new TreeNode(rootVal);
    root.left = buildTree(Arrays.copyOfRange(preorder, 1, mid + 1), Arrays.copyOfRange(inorder, 0, mid));
    root.right = buildTree(Arrays.copyOfRange(preorder, mid + 1, preorder.length), Arrays.copyOfRange(inorder, mid + 1, inorder.length));
    return root;
}

def build_tree(preorder, inorder):
    if not preorder: return None
    root_val = preorder[0]
    mid = inorder.index(root_val)
    root = TreeNode(root_val)
    root.left = build_tree(preorder[1:mid + 1], inorder[:mid])
    root.right = build_tree(preorder[mid + 1:], inorder[mid + 1:])
    return root

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

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> index;
    for (int i = 0; i < (int)inorder.size(); i++) index[inorder[i]] = i;
    int pre = 0;
    function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        TreeNode* root = new TreeNode(preorder[pre++]);
        int mid = index[root->val];
        root->left = build(lo, mid - 1);
        root->right = build(mid + 1, hi);
        return root;
    };
    return build(0, (int)inorder.size() - 1);
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> index = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) index.put(inorder[i], i);
    int[] pre = {0};
    return build(preorder, index, pre, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, Map<Integer, Integer> index, int[] pre, int lo, int hi) {
    if (lo > hi) return null;
    TreeNode root = new TreeNode(preorder[pre[0]++]);
    int mid = index.get(root.val);
    root.left = build(preorder, index, pre, lo, mid - 1);
    root.right = build(preorder, index, pre, mid + 1, hi);
    return root;
}

def build_tree(preorder, inorder):
    index = {}
    for i, v in enumerate(inorder): index[v] = i
    pre = 0
    def build(lo, hi):
        nonlocal pre
        if lo > hi: return None
        root = TreeNode(preorder[pre])
        pre += 1
        mid = index[root.val]
        root.left = build(lo, mid - 1)
        root.right = build(mid + 1, hi)
        return root
    return build(0, len(inorder) - 1)

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const index = new Map<number, number>();
  inorder.forEach((v, i) => index.set(v, i));
  let pre = 0;
  const build = (lo: number, hi: number): TreeNode | null => {
    if (lo > hi) return null;
    const root = new TreeNode(preorder[pre++]);
    const mid = index.get(root.val)!;
    root.left = build(lo, mid - 1);
    root.right = build(mid + 1, hi);
    return root;
  };
  return build(0, inorder.length - 1);
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty()) return nullptr;
    TreeNode* root = new TreeNode(preorder[0]);
    vector<TreeNode*> stack = {root};
    int inIdx = 0;
    for (int i = 1; i < (int)preorder.size(); i++) {
        TreeNode* node = stack.back();
        TreeNode* child = new TreeNode(preorder[i]);
        if (node->val != inorder[inIdx]) {
            node->left = child;
        } else {
            while (!stack.empty() && stack.back()->val == inorder[inIdx]) {
                node = stack.back(); stack.pop_back();
                inIdx++;
            }
            node->right = child;
        }
        stack.push_back(child);
    }
    return root;
}

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 inIdx = 0;
    for (int i = 1; i < preorder.length; i++) {
        TreeNode node = stack.peek();
        TreeNode child = new TreeNode(preorder[i]);
        if (node.val != inorder[inIdx]) {
            node.left = child;
        } else {
            while (!stack.isEmpty() && stack.peek().val == inorder[inIdx]) {
                node = stack.pop();
                inIdx++;
            }
            node.right = child;
        }
        stack.push(child);
    }
    return root;
}

def build_tree(preorder, inorder):
    if not preorder: return None
    root = TreeNode(preorder[0])
    stack = [root]
    in_idx = 0
    for i in range(1, len(preorder)):
        node = stack[-1]
        child = TreeNode(preorder[i])
        if node.val != inorder[in_idx]:
            node.left = child
        else:
            while stack and stack[-1].val == inorder[in_idx]:
                node = stack.pop()
                in_idx += 1
            node.right = child
        stack.append(child)
    return root

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

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int pre = 0;
    int inn = 0;
    function<TreeNode*(long long)> build = [&](long long stop) -> TreeNode* {
        if (pre >= (int)preorder.size()) return nullptr;
        if (inn < (int)inorder.size() && inorder[inn] == stop) {
            inn++;
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[pre++]);
        root->left = build(root->val);
        root->right = build(stop);
        return root;
    };
    return build(LLONG_MIN);
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int[] pos = {0, 0};
    return build(preorder, inorder, pos, Long.MIN_VALUE);
}

private TreeNode build(int[] preorder, int[] inorder, int[] pos, long stop) {
    if (pos[0] >= preorder.length) return null;
    if (pos[1] < inorder.length && inorder[pos[1]] == stop) {
        pos[1]++;
        return null;
    }
    TreeNode root = new TreeNode(preorder[pos[0]++]);
    root.left = build(preorder, inorder, pos, root.val);
    root.right = build(preorder, inorder, pos, stop);
    return root;
}

def build_tree(preorder, inorder):
    pre = 0
    inn = 0
    def build(stop):
        nonlocal pre, inn
        if pre >= len(preorder): return None
        if inn < len(inorder) and inorder[inn] == stop:
            inn += 1
            return None
        root = TreeNode(preorder[pre])
        pre += 1
        root.left = build(root.val)
        root.right = build(stop)
        return root
    return build(None)

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  let pre = 0;
  let inn = 0;
  const build = (stop: number | null): TreeNode | null => {
    if (pre >= preorder.length) return null;
    if (inn < inorder.length && inorder[inn] === stop) {
      inn++;
      return null;
    }
    const root = new TreeNode(preorder[pre++]);
    root.left = build(root.val);
    root.right = build(stop);
    return root;
  };
  return build(null);
}