cf.completefrontend
TREES & TRIES · CORE

Building a tree from traversals

Rebuild a binary tree from its preorder and inorder lists by taking each root from preorder and splitting inorder around it.

Time O(n)Space O(n)6 practice problemsStep-through picture

The idea

A single list of values usually can't describe a tree's shape: many different trees give the same preorder. But two lists together can. Preorder (node, left, right) tells you which value is the root. Inorder (left, node, right) tells you which values are on its left and which are on its right.

So the first value of preorder is the root. Find it in inorder: everything before it belongs to the left subtree, and everything after it belongs to the right subtree. Then do the same for each side, recursively.

Preorder lists the whole left subtree before the right subtree, so if you read preorder from left to right with one moving index called next, each value you read is the root of the subtree you are building right now.

An everyday example

Seating guests from two lists

You get two lists for a family photo. The first says who is the most senior person in each group, oldest first. The second shows everyone standing in a line from left to right. Take the most senior person from the first list. In the line, everyone to their left is in their left group and everyone to their right is in their right group. Repeat inside each group until everyone has a spot.

How the example maps to the code
In the exampleIn the code
The seniority listpreorder, read with next
The left-to-right lineinorder
Finding a person's spot in the linemid = indexOf.get(val)
People left of thembuild(low, mid - 1)
People right of thembuild(mid + 1, high)

From the slow way to building a tree from traversals

  1. Given only a preorder list, could you rebuild the tree? Try [1, 2]: 2 could be the left child or the right child of 1. One list loses the shape. Trying every possible shape and checking each one is hopeless, since there are already 42 different binary tree shapes with only 5 nodes.
  2. Two lists together pin the shape down. Preorder always starts with the root. Inorder puts the root between its left subtree and its right subtree. So once you know the root, finding it in inorder tells you exactly which values are on its left and which are on its right.
  3. That turns one big problem into two smaller problems of the same kind: build the left subtree from its part of the lists, and the right subtree from its part. Searching inorder for each root would cost O(n) every time, so first build a Map from each value to its inorder index, and each lookup becomes O(1).
  4. Finally, preorder lists the root, then the whole left subtree, then the whole right subtree, which is exactly the order the recursion builds things in. So a single counter, next, moving forward through preorder always points at the root of the subtree being built. Recursion on inorder ranges plus one moving preorder index is building a tree from traversals.

How it works

  1. Store each value's position in inorder in a map indexOf, so finding a root is O(1).
  2. Keep next, the index of the next unused value in preorder. It starts at 0.
  3. build(low, high) builds the subtree whose values are inorder[low..high]. If low > high, it is empty: return null.
  4. Take val = preorder[next] and move next forward. val is this subtree's root.
  5. Find mid = indexOf.get(val). Values low..mid - 1 form the left subtree and mid + 1..high the right subtree.
  6. Build the left subtree first, then the right one, because that is the order preorder lists them. Return the node.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function buildTree(preorder, inorder) {
  2. const indexOf = new Map();
  3. inorder.forEach((val, i) => indexOf.set(val, i));
  4. let next = 0;
  5. function build(low, high) {
  6. if (low > high) return null;
  7. const val = preorder[next];
  8. next++;
  9. const node = new TreeNode(val);
  10. const mid = indexOf.get(val);
  11. node.left = build(low, mid - 1);
  12. node.right = build(mid + 1, high);
  13. return node;
  14. }
  15. return build(0, inorder.length - 1);
  16. }

How fast it is

TimeO(n)
Extra memoryO(n)

Each value becomes one node with an O(1) map lookup. The map holds n entries and the recursion is at most n deep.

  • Best caseO(n)

    Any input with distinct values: each value is read once from preorder and looked up once in the map.

  • Average caseO(n)

    The same work for every shape: n nodes made and n + 1 empty ranges checked.

  • Worst caseO(n)

    A chain, such as preorder [5, 4, 3, 2, 1] with inorder [1, 2, 3, 4, 5]. The time is still O(n), but the recursion goes n levels deep.

Common mistakes

  • Building the right subtree before the left one while reading preorder forward. The roots get used in the wrong order.
  • Slicing new arrays for every call, like inorder.slice(0, mid). It works, but copying makes it O(n^2). Pass index ranges instead.
  • Using this when values repeat. indexOf can't tell two equal values apart, so the tree comes out wrong. It needs unique values.
  • Off-by-one ranges: the left side is low..mid - 1 and the right side is mid + 1..high; the root at mid belongs to neither.

When to use it

Look for these clues in a problem:

  • You are given two traversal orders and asked for the tree.
  • You get a flat list of items with parent ids and must nest them.
  • You are given a sorted list and asked for a balanced search tree.
  • Values are unique, so each value's position in one list can be found in the other.

Check yourself

Answer each one in your head first, then open it.

Why do the values need to be distinct?

The map turns each value into one inorder position. With repeated values, that position may belong to another node, and the split puts nodes on the wrong side.

In the trace, why is preorder[next] equal to 7 when the root's right side starts?

The left call used 9 and 4, the whole left subtree, moving next from 1 to 3. preorder[3] is 7, the first value after the left subtree.

How many calls return null when building a tree of n nodes?

n + 1, one per empty child slot. In the trace, 6 nodes gave 7 empty calls.

What goes wrong if you swap the two recursive calls?

The right call would read the left subtree's root from preorder. That value isn't in the right range, so the tree comes out wrong or the ranges stop making sense.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule for a call build(low, high): the values inorder[low..high] are exactly the nodes of one subtree, and preorder[next] is that subtree's root. At the first call the range is the whole list and next = 0, which points at the whole tree's root, so the rule holds.

Inside a call, the root's inorder index mid splits the range. By the definition of inorder, inorder[low..mid-1] is the left subtree and inorder[mid+1..high] is the right one. After next++, preorder continues with the entire left subtree, so the left call's rule holds. That call uses up exactly as many preorder values as the left subtree has nodes, so when it returns, next points at the right subtree's root and the right call's rule holds too.

Every call either uses one preorder value and makes one node, or meets an empty range and returns null, and each range is smaller than its parent's, so the recursion ends. Each of the n values is used once and placed with the correct left and right parts, so the result is the one tree that has both traversals. That tree is unique as long as the values are distinct.

Going deeper

3 more ideas

Why reading preorder in order works

Preorder lists a root, then its entire left subtree, then its entire right subtree. Our build makes a root, then builds the whole left subtree, then the whole right one. Because the two follow the same order, the value at next is always the root of the subtree being built.

Other pairs and flat lists

Postorder plus inorder also works: read postorder from the end, which gives roots, and build the right subtree before the left. Preorder plus postorder is not enough on its own, because a node with one child could have it on either side. For a flat list of { id, parentId } rows, put every item in a map by id, then attach each one to its parent's children in one pass.

Time and memory

The map makes each root lookup O(1), and each value becomes a node once, so the time is O(n). Without the map, searching inorder for each root costs O(n) and the total is O(n^2). Memory is the map plus the recursion depth: O(n).

Work it by hand

Every step in a table, with why

Rebuild a 6-node tree from its preorder and inorder lists. Every call is shown, including the 7 that meet an empty range.

preorder = [3, 9, 4, 7, 5, 1], inorder = [4, 9, 3, 5, 7, 1]

Stepbuild(low, high)valmidnext afterWhat happensWhy
1build(0, 5)321left 0..1, right 3..5The whole inorder range. The next preorder value, 3, is the root. It sits at inorder index 2, so [4, 9] is its left side and [5, 7, 1] its right side.
2build(0, 1)912left 0..0, right 2..1Building the left subtree of 3. next points at 9, so 9 is this subtree's root. Its index 1 leaves [4] on its left and nothing on its right.
3build(0, 0)403left 0..-1, right 1..0A range of one value: 4 becomes a node, and both of its sides are empty ranges.
4build(0, -1)--3empty: nulllow > high, so 4 has no left child. next doesn't move, because no value was used.
5build(1, 0)--3empty: null4 has no right child either.
6build(2, 1)--3empty: null9 has no right child: nothing in 0..1 comes after index 1.
7build(3, 5)744left 3..3, right 5..5Back at the root, now its right side. next has moved past 3, 9, and 4, the root and its whole left subtree, so it points at 7.
8build(3, 3)535left 3..2, right 4..35 is alone in its range, so it becomes a leaf.
9build(3, 2)--5empty: null5 has no left child.
10build(4, 3)--5empty: null5 has no right child.
11build(5, 5)156left 5..4, right 6..51 is the right child of 7.
12build(5, 4)--6empty: null1 has no left child.
13build(6, 5)--6empty: nullThe last empty range. next equals 6, the length of preorder, so every value was used exactly once.

The tree [3, 9, 7, 4, null, 5, 1]: root 3, left child 9 with left child 4, and right child 7 with children 5 and 1. That's 13 calls: 6 that made a node and 7 that returned null, one per empty child slot.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Building a tree from traversalsO(n)O(n)You have inorder plus preorder (or postorder), and the values are distinct.
Same recursion, searching inorder for each rootO(n²)O(h)Tiny inputs where you'd rather not build a map. A chain makes every search scan far.
Map from id to nodeO(n)O(n)The data is flat rows with parent ids, as from a database or an API, not traversal lists.

Extra memory: O(n): the indexOf map holds n entries, and the recursion uses O(h) stack, up to n for a chain. The tree itself is the output.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Building a tree from traversals and the other approaches, on a scale where each line up is 10 times more steps.
  • Building a tree from traversals, Map from id to node O(n)
  • Same recursion, searching inorder for each root O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Building a tree from traversals101,0001 million
Same recursion, searching inorder for each root1001 million1 trillion
Map from id to node101,0001 million

Inputs that need care

4 tricky inputs
Empty lists: preorder = [], inorder = []
build(0, -1) meets low > high at once and returns null: an empty tree.
Duplicate values, like [2, 2] in both lists
The map keeps only the last index of each value, so a split can be wrong. With duplicates, the tree isn't even unique. Build from node ids instead of values.
Lists that don't match, like preorder [1, 2] and inorder [1, 3]
indexOf.get(2) is undefined, so mid - 1 is NaN. low > NaN is always false, so no range ever looks empty, and the recursion runs until the stack overflows. Check that both lists hold the same values first.
A chain 20,000 nodes deep
The recursion goes 20,000 calls deep and may overflow the stack. An iterative version with an explicit stack of nodes still waiting for a right child avoids that.

Variations and follow-ups

Twists interviewers add

Inorder and postorder

Postorder ends with the root, so read it from the end with next moving backward. Build the right subtree before the left one, because reading backward meets the right subtree first.

Search tree from preorder alone

For a BST, the inorder list is just the sorted values, so preorder is enough. Pass an upper bound instead: build(bound) takes preorder[next] only if it's below bound, builds the left side with bound = val, and builds the right side with the parent's bound. It's O(n) with no map.

Flat rows to a tree

Data often arrives as rows like { id, parentId }. Put each row in a Map by id with an empty children array, then loop once and push each row into its parent's children. The row with no parent is the root. It's O(n) and needs no recursion.

Preorder and postorder of a full tree

If every node has 0 or 2 children, preorder plus postorder is enough. The value right after the root in preorder is the left child, and finding it in postorder tells you how big the left subtree is.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "construct", "build the tree from", "given preorder and inorder", or flat rows with a parentId.
  • Explain the split with a small drawing: the first preorder value is the root, and finding it in inorder cuts the list into a left part and a right part. Mention the map early, because interviewers often ask how to avoid the O(n²) search.
  • Explain why node.left must be built before node.right: the shared next reads preorder in order, and preorder lists the left subtree first.
  • Expect "does preorder plus postorder work?". Not in general: 1 with a left child 2 and 1 with a right child 2 both give preorder [1, 2] and postorder [2, 1].

Where frontend code uses it

The same idea in real UI code
  • APIs often return comments, categories, or menu items as a flat list with a parentId. The UI nests them into a tree before rendering a thread or a menu.
  • An HTML parser builds the DOM tree from a flat stream of opening and closing tags.
  • A table of contents is built from a flat list of headings (h2, h3, ...) by nesting each heading under the last heading of a higher level.

Related algorithms