These are the notes for DSA episode 42. In episode 41 we needed a # for every empty spot to rebuild a tree from one list. Today there are no markers: you get two plain lists, the preorder and the inorder traversal of the same tree, and together they fix the tree exactly. We start from a real-life story (a team chart rebuilt from two lists), recap the traversals, find the key split (the first preorder value is the root; its place in inorder splits the left and right subtrees), code it the obvious way with a linear search, watch it hit Time Limit Exceeded on a big tree, and then solve it in O(n) with a HashMap and one moving pointer. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
A school sports team is organised like a tree: the captain on top, and each person leads at most two groups, one on the left and one on the right. The chart is lost, but two lists survive:
- the coach's list of the order people were called on stage: always the leader first, then everyone in the left group, then everyone in the right group;
- the team photo, names from left to right: the left group stands left of their leader, the right group to the right.
From these two lists alone you can redraw the chart exactly.
| With the team | In a binary tree |
|---|---|
| Order called on stage (leader, left group, right group) | preorder (root, left, right) |
| Left to right on the photo (left group, leader, right group) | inorder (left, root, right) |
| The captain, called first | the root = preorder[0] |
| Who stands left of the captain in the photo | the left subtree |
| Who stands right of the captain | the right subtree |
Every word, from zero
- Binary tree, node, root, child, leaf: from episode 36.
- Preorder: visit the root, then the whole left subtree, then the whole right subtree.
- Inorder: visit the whole left subtree, then the root, then the whole right subtree.
- Segment: a slice of an array from index
loto indexhi(inclusive). We describe parts of the tree as segments instead of copying arrays. - Distinct values: no value appears twice. Without this, a value's position in inorder is not unique and neither is the tree.
- Linear search: checking items one by one until you find the one you want: O(length).
HashMap: a map from keys to values with O(1) averageputandget, like a phone's contact list: give it a name, get the number, no scrolling.- Why two lists: one traversal alone loses the shape. In episode 41, the preorder
1,2,3fitted two different trees.
Problem statement
Given two integer arrays preorder and inorder of the same binary tree, build the tree and return its root.
| preorder | inorder | tree |
|---|---|---|
[3, 9, 20, 15, 7] |
[9, 3, 15, 20, 7] |
[3, 9, 20, null, null, 15, 7] |
[-1] |
[-1] |
[-1] |
Constraints: 1 … 3000 nodes, values −3000 … 3000, all values distinct.
To print a tree we reuse episode 41's preorder string with # for null:
static String ser(Node n) {
if (n == null) return "#,";
return n.val + "," + ser(n.left) + ser(n.right);
}
The key split
- Preorder starts with the root: 3.
- Find 3 in inorder:
9 | 3 | 15 20 7. Everything before it (9) is the left subtree, everything after it (15 20 7) the right subtree. - The sizes cut preorder too: after the root, 1 value for the left (
9), then 3 for the right (20 15 7). - Repeat on each part: the right part's preorder starts with 20, so 20 is its root; in its inorder
15 | 20 | 7→ 15 left, 7 right.
If the root sits at position k of the inorder segment [iLo, iHi], the left subtree has leftSize = k - iLo values.
| Part | preorder starts at | inorder segment |
|---|---|---|
| left subtree | pLo + 1 |
[iLo, k - 1] |
| right subtree | pLo + 1 + leftSize |
[k + 1, iHi] |
Brute force: search for the root in every call
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
}
static String ser(Node n) {
if (n == null) return "#,";
return n.val + "," + ser(n.left) + ser(n.right);
}
static Node slow(int[] pre, int pLo, int[] in, int iLo, int iHi) {
if (iLo > iHi) return null;
Node root = new Node(pre[pLo]);
int k = iLo;
while (in[k] != root.val) k++;
int leftSize = k - iLo;
root.left = slow(pre, pLo + 1, in, iLo, k - 1);
root.right = slow(pre, pLo + 1 + leftSize, in, k + 1, iHi);
return root;
}
public static void main(String[] args) {
int[] pre = {3, 9, 20, 15, 7};
int[] in = {9, 3, 15, 20, 7};
System.out.println(ser(slow(pre, 0, in, 0, in.length - 1)));
System.out.println(ser(slow(new int[]{-1}, 0, new int[]{-1}, 0, 0)));
}
}
Real output:
3,9,#,#,20,15,#,#,7,#,#,
-1,#,#,
Root 3, left 9, right 20 with children 15 and 7: correct.
A big tree: Time Limit Exceeded
A chain of 4,500 nodes (each the left child of the one before) with a complete tree 21 levels deep at the bottom: 2,101,651 nodes numbered 1, 2, 3, … (all distinct). walk records both traversals in one pass:
static int next = 1;
static Node full(int d) {
if (d == 0) return null;
Node n = new Node(next++);
n.left = full(d - 1);
n.right = full(d - 1);
return n;
}
static int p, q;
static void walk(Node n, int[] pre, int[] in) {
if (n == null) return;
pre[p++] = n.val;
walk(n.left, pre, in);
in[q++] = n.val;
walk(n.right, pre, in);
}
// in main:
Node top = new Node(next++), cur = top;
for (int j = 1; j < 4500; j++) {
cur.left = new Node(next++);
cur = cur.left;
}
cur.left = full(21);
int n = next - 1;
int[] pre = new int[n], in = new int[n];
walk(top, pre, in);
long t0 = System.nanoTime();
Node back = slow(pre, 0, in, 0, n - 1);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(n + " nodes, root " + back.val + ", " + ms + " ms");
In the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 s). Without a limit it printed 2101651 nodes, root 1, 10385 ms.
Why the brute force is slow
- Every chain node has its whole subtree on the left, so in inorder it comes after all of it, at the far end of its segment.
- The scan starts at the beginning and walks past all ~21 lakh nodes below before finding the root.
- 4,500 chain nodes × 21 lakh steps ≈ 950 crore steps. In general O(n · h); on a plain chain O(n²).
The key insight: a map of positions and one moving pointer
- A
HashMapfrom value to inorder index, filled once:pos.put(inorder[j], j). Thenpos.get(v)is O(1): the scan is gone. - One preorder pointer
pi. The recursion builds the root, then the whole left subtree, then the whole right subtree: exactly preorder. So each new node just takespre[pi++]; we never compute where each part of preorder starts. - Build the left before the right, so the pointer hands out values in preorder.
Building example 1 (pos: 9→0, 3→1, 15→2, 20→3, 7→4):
| pi | value | its range | pos | left range | right range |
|---|---|---|---|---|---|
| 0 | 3 | [0, 4] | 1 | [0, 0] | [2, 4] |
| 1 | 9 | [0, 0] | 0 | empty | empty |
| 2 | 20 | [2, 4] | 3 | [2, 2] | [4, 4] |
| 3 | 15 | [2, 2] | 2 | empty | empty |
| 4 | 7 | [4, 4] | 4 | empty | empty |
The optimal solution in Java
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
}
static String ser(Node n) {
if (n == null) return "#,";
return n.val + "," + ser(n.left) + ser(n.right);
}
static int[] pre;
static int pi;
static Map<Integer, Integer> pos = new HashMap<>();
static Node buildTree(int[] preorder, int[] inorder) {
pre = preorder;
pi = 0;
pos.clear();
for (int j = 0; j < inorder.length; j++) pos.put(inorder[j], j);
return build(0, inorder.length - 1);
}
static Node build(int lo, int hi) {
if (lo > hi) return null;
Node root = new Node(pre[pi++]);
int k = pos.get(root.val);
root.left = build(lo, k - 1);
root.right = build(k + 1, hi);
return root;
}
public static void main(String[] args) {
int[] pre = {3, 9, 20, 15, 7};
int[] in = {9, 3, 15, 20, 7};
System.out.println(ser(buildTree(pre, in)));
System.out.println(ser(buildTree(new int[]{-1}, new int[]{-1})));
System.out.println(ser(buildTree(new int[]{1, 2, 3}, new int[]{3, 2, 1})));
System.out.println(ser(buildTree(new int[]{1, 2, 3}, new int[]{1, 2, 3})));
}
}
Real output:
3,9,#,#,20,15,#,#,7,#,#,
-1,#,#,
1,2,3,#,#,#,#,
1,#,2,#,3,#,#,
The same preorder 1, 2, 3 gives a left chain with inorder 3, 2, 1 and a right chain with inorder 1, 2, 3: the second list decides the shape.
The big tree in about a second
The same 2,101,651-node tree with buildTree: real output 2101651 nodes, root 1, 753 ms on a laptop (1 to 1.5 seconds in the SyntaxPilot compiler). Most of the time is spent filling the HashMap.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
Node(int v) : val(v) {}
};
string ser(Node* n) {
if (!n) return "#,";
return to_string(n->val) + "," + ser(n->left) + ser(n->right);
}
vector<int> pre;
int pi;
unordered_map<int, int> pos;
Node* build(int lo, int hi) {
if (lo > hi) return nullptr;
Node* root = new Node(pre[pi++]);
int k = pos[root->val];
root->left = build(lo, k - 1);
root->right = build(k + 1, hi);
return root;
}
Node* buildTree(const vector<int>& preorder, const vector<int>& inorder) {
pre = preorder; pi = 0; pos.clear();
for (int j = 0; j < (int)inorder.size(); j++) pos[inorder[j]] = j;
return build(0, (int)inorder.size() - 1);
}
int main() {
cout << ser(buildTree({3, 9, 20, 15, 7}, {9, 3, 15, 20, 7})) << "\n";
cout << ser(buildTree({-1}, {-1})) << "\n";
cout << ser(buildTree({1, 2, 3}, {3, 2, 1})) << "\n";
cout << ser(buildTree({1, 2, 3}, {1, 2, 3})) << "\n";
}
Real output (g++ -O2 -std=c++17): the same four lines as Java.
The same solution in Python
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def ser(n):
if n is None:
return "#,"
return f"{n.val}," + ser(n.left) + ser(n.right)
def build_tree(preorder, inorder):
pos = {v: j for j, v in enumerate(inorder)}
it = iter(preorder) # one pointer that only moves forward
def build(lo, hi):
if lo > hi:
return None
root = Node(next(it))
k = pos[root.val]
root.left = build(lo, k - 1) # left first: preorder order
root.right = build(k + 1, hi)
return root
return build(0, len(inorder) - 1)
print(ser(build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])))
print(ser(build_tree([-1], [-1])))
print(ser(build_tree([1, 2, 3], [3, 2, 1])))
print(ser(build_tree([1, 2, 3], [1, 2, 3])))
Real output: the same four lines. A dict is Python's hash map, and iter + next is the moving pointer.
Two real bugs
Bug 1: building the right subtree first
root.right = build(k + 1, hi);
root.left = build(lo, k - 1);
Real output on example 1:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at Main.build(Main.java:25)
...
The pointer handed 9, the next preorder value, to the right range, where 9 does not belong; the ranges and the pointer fell out of step and pi ran off the end of preorder. With one forward pointer, always build the left first. (With inorder + postorder it is the opposite: read postorder backwards and build the right first; see practice 1.)
Bug 2: using k as the size of the left part
root.right = slow(pre, pLo + 1 + k, in, k + 1, iHi); // should be pLo + 1 + leftSize
Real output on example 1:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 5
at Main.slow(Main.java:15)
...
k is a position in the whole array, not a size. In a right part iLo is not 0, so k overshoots. The left size is always k - iLo.
Also: very deep trees
build recurses once per level. On a chain tens of thousands of levels deep, Java throws StackOverflowError (Python: RecursionError). An iterative version with an explicit stack avoids it.
Complexity
| Approach | Time | Space | Big tree (2.1 million nodes) |
|---|---|---|---|
| Linear search for the root | O(n · h), O(n²) on a chain | O(h) recursion | 10.4 s → TLE |
HashMap + moving pointer |
O(n) | O(n) map + O(h) recursion | 0.75–1.5 s |
n = number of nodes, h = height. The map trades O(n) memory for the speed.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Build right before left (with a forward pointer) | ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 |
the pointer hands out values in preorder | build the left subtree first |
pLo + 1 + k |
ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 5 |
k is a position, not a size |
leftSize = k - iLo |
| Linear search for the root | Time Limit Exceeded on deep trees | a fresh scan in every call | HashMap value → index |
Copying sub-arrays with Arrays.copyOfRange |
slow, lots of memory | O(n) copies per level | pass lo/hi indices |
Not resetting pi / not clearing pos |
wrong trees on a second call | static state left over | reset both in buildTree |
| Duplicate values | the tree is not unique | the map keeps one index per value | the problem promises distinct values |
Mini project: the team-chart rebuilder
Store a team as Player nodes with names. Print its two lists (called order = preorder, photo order = inorder) as comma-separated names. Then read the two lists back, rebuild the chart with the HashMap method, and print it sideways (right subtree on top, indented by depth). Try removing one name from the photo list and make your program print a clear error instead of crashing.
Practice
- Build from inorder and postorder (LeetCode 106).
Solution
Postorder ends with the root. Read it backwards with a pointer that moves left; backwards postorder is root, right, left, so build the right subtree first.
static int[] post; static int qi;
static Map<Integer, Integer> pos = new HashMap<>();
static Node fromPost(int[] inorder, int[] postorder) {
post = postorder; qi = postorder.length - 1; pos.clear();
for (int j = 0; j < inorder.length; j++) pos.put(inorder[j], j);
return bp(0, inorder.length - 1);
}
static Node bp(int lo, int hi) {
if (lo > hi) return null;
Node root = new Node(post[qi--]);
int k = pos.get(root.val);
root.right = bp(k + 1, hi);
root.left = bp(lo, k - 1);
return root;
}
fromPost({9, 3, 15, 20, 7}, {9, 15, 7, 20, 3}) → 3,9,#,#,20,15,#,#,7,#,#,. Real output.
- Build a BST from its preorder alone (LeetCode 1008).
Solution
In a binary search tree the inorder is just the sorted values, so you do not need it: a value belongs at the current spot only if it fits the allowed range.
static int[] pre; static int pi;
static Node bstFromPre(int[] p) { pre = p; pi = 0; return bb(Integer.MIN_VALUE, Integer.MAX_VALUE); }
static Node bb(int lo, int hi) {
if (pi == pre.length || pre[pi] < lo || pre[pi] > hi) return null;
Node n = new Node(pre[pi++]);
n.left = bb(lo, n.val - 1);
n.right = bb(n.val + 1, hi);
return n;
}
bstFromPre({8, 5, 1, 7, 10, 12}) → 8,5,1,#,#,7,#,#,10,#,12,#,#,. Real output. O(n).
- Why can preorder + postorder not always decide the tree?
Answer
Take root 1 with a single child 2. If 2 is the left child: preorder 1, 2, postorder 2, 1. If 2 is the right child: preorder 1, 2, postorder 2, 1. The same two lists, two trees. Neither list tells you which side a lone child is on; inorder does (it puts the root before or after the child). LeetCode 889 accepts any valid answer for this reason, and it is unique only for a full binary tree (every node has 0 or 2 children).
Quick quiz
pre = {4, 2, 1, 3, 6}, in = {1, 2, 3, 4, 6}. What is the root's left child: 1, 2, 3 or 6?
Answer
2. The root is pre[0] = 4. In inorder, 1, 2 and 3 are on its left; the left part's preorder is 2, 1, 3, so its root is 2.
Interview questions
- Why are both traversals needed? Preorder tells you the root of every part; inorder tells you which values are left and right of it. Preorder alone loses the shape.
- Why must values be distinct? The method finds the root by its value in inorder; with duplicates the position (and the tree) is ambiguous.
- Why does the pointer approach require building the left first? The recursion must visit nodes in exactly preorder order, which is root, left, right.
- Time and space? O(n) time with the map; O(n) space for the map plus O(h) recursion. Without the map, O(n · h) time.
- How would you avoid recursion? Use a stack: push nodes while following preorder, and pop while the top matches the next inorder value (attaching the next node as a right child). O(n), no stack overflow.
- What changes for inorder + postorder? The root is the last value of postorder; read it backwards and build right before left.
Glossary
| Term | Meaning |
|---|---|
| Preorder | Root, then left subtree, then right subtree |
| Inorder | Left subtree, then root, then right subtree |
| Postorder | Left subtree, right subtree, then root |
| Segment | A slice of an array from index lo to hi |
| Distinct | No value appears twice |
| Linear search | Checking items one by one until you find the target |
HashMap |
Key → value map with O(1) average put and get |
leftSize |
The number of values in the left subtree: k - iLo |
| Pointer (index) | An int that marks the next value to read; here it only moves forward |
| Binary search tree (BST) | Left values smaller, right values bigger than the node |
| O(n · h), O(n²) | Running time growing with nodes × height; squared on a chain |
| Time Limit Exceeded (TLE) | The program was stopped for running too long (8 s in the SyntaxPilot compiler) |
ArrayIndexOutOfBoundsException |
Thrown when an array index is below 0 or ≥ its length |
StackOverflowError |
Java's error when recursion goes too deep for the call stack |
Summary
- One traversal loses the shape; preorder + inorder fix it (with distinct values).
pre[0]is the root; its positionkin inorder splits left and right, andleftSize = k - iLocuts preorder.- A linear search for the root in every call is O(n · h): TLE on a deep tree.
- A
HashMapvalue → inorder index and one preorder pointer that builds left before right: O(n) time, O(n) space.
Next episode: Heaps: top K frequent elements.