Tree Construction from Traversals

Reconstruction problems all rest on the same two-part observation:

One traversal tells you the roots. Another tells you the split.

Preorder and postorder both reveal which element is a subtree’s root — preorder at the front, postorder at the back. Inorder reveals where the left subtree ends and the right begins, because everything before the root is left and everything after is right.

Put them together and the tree is determined. Each alone is not enough, and knowing why is the first question you will be asked.

What you’ll learn

• Why a single traversal is ambiguous, and which pairs are sufficient.
• The recursive template, and the index map that removes the $O(n)$ search.
• The shared index trick — why one moving pointer beats slicing arrays.
• Why postorder must build the right subtree first.
• Three real LeetCode problems solved in the browser: 105, 106, 654.

The cue

You are looking at a construction problem when…

• You are given two traversals and asked for the tree — 105, 106, 889.
• A tree is defined by a rule over an array — 654 (maximum), 1008 (BST from preorder), 108 (balanced BST from a sorted array).
• Serialize then deserialize — 297, 449. See Serialize, Compare and Subtree.
• You must verify a sequence could come from a particular tree shape — 255, 331.

Why one traversal is not enough

The preorder [1, 2] is produced by two different trees:

text

  1            1
 /              \
2                2

Both give preorder [1, 2]. Nothing in the sequence records whether 2 was a left or a right child, so reconstruction is impossible.

Adding inorder disambiguates: inorder [2, 1] means 2 precedes the root, so it is the left child; inorder [1, 2] means it follows, so it is the right child.

Which pairs work:

Pair	Works?	Why
preorder + inorder	✅	Root from preorder, split from inorder
postorder + inorder	✅	Root from postorder’s end, split from inorder
preorder + postorder	⚠️ only for full trees	Without inorder there is no split point; unique only if every node has 0 or 2 children (LC 889)
any one alone	❌	No split information

The exception worth knowing: for a BST, preorder alone is enough, because sorting it gives you the inorder. That is LC 1008.

Visual intuition

The two arrays the problem hands you are the outputs of these two walks over the tree you have to rebuild. Reading them side by side is what the algorithm does.

Pre-order — the walk that tells you which node is the root of every window:

treePre-order emits [3, 9, 20, 15, 7] — every element is a root, in the order you need themroot, left, right

call stack

3

1def preorder(node, out):2    if node is None:3        return4    out.append(node.val)      # visit5    preorder(node.left, out)6    preorder(node.right, out)7    out.append(node.val)      # visit

node3stack depth1

enterEnter 3. The recursive call is pushed onto the stack, which is now 1 frame deep.

Play‹›1/16⟲

Pre-order visits a node before either subtree, so its elements arrive in exactly the order the recursion wants to create nodes. That is why a single ever-advancing pointer into the pre-order array is enough -- it never has to move backwards.

In-order — the walk that tells you how big each subtree is:

treeIn-order emits [9, 3, 15, 20, 7] — the root splits it into left and rightleft, root, right

call stack

3

1def inorder(node, out):2    if node is None:3        return4    inorder(node.left, out)5    out.append(node.val)      # visit6    inorder(node.right, out)

node3stack depth1

enterEnter 3. The recursive call is pushed onto the stack, which is now 1 frame deep.

Play‹›1/16⟲

Find 3 in the in-order array at position 1: everything before it (just 9) is the left subtree, everything after (15, 20, 7) is the right. Neither array alone is enough -- pre-order gives roots without sizes, in-order gives sizes without roots.

The template — preorder + inorder

build_pre_in.py

def build_tree(preorder, inorder):
    index = {v: i for i, v in enumerate(inorder)}   # value -> inorder position
    pre = 0                                          # shared, ever-advancing pointer
 
    def helper(left, right):
        """Build from the inorder window [left, right]."""
        nonlocal pre
        if left > right:
            return None
 
        root_val = preorder[pre]      # preorder's next element is this root
        pre += 1
        node = TreeNode(root_val)
 
        mid = index[root_val]         # where the root sits in inorder
        node.left = helper(left, mid - 1)     # LEFT first -- matches preorder order
        node.right = helper(mid + 1, right)
        return node
 
    return helper(0, len(inorder) - 1)

Two design choices carry the complexity:

The index map: $O(n^2)$ becomes $O(n)$

Without index, finding the root’s position needs inorder.index(root_val) — an $O(n)$ scan per node, so $O(n^2)$ overall. On a degenerate tree with n = 3000 that is nine million operations.

Precomputing a value-to-position dict makes each lookup $O(1)$ and the whole build $O(n)$. This is the single most important optimisation in these problems, and it assumes distinct values — which LC 105 and 106 both guarantee. With duplicates the map is ambiguous and reconstruction is not generally unique.

One shared pointer, not array slicing

The tempting version slices:

python

root = preorder[0]
mid = inorder.index(root)
node.left = build(preorder[1:mid+1], inorder[:mid])       # copies!
node.right = build(preorder[mid+1:], inorder[mid+1:])

It reads beautifully and is $O(n^2)$ time and $O(n^2)$ space, because every level copies the arrays. It also makes the preorder-slicing bounds easy to get wrong.

A single pre pointer that only ever advances avoids all of it. It works because preorder visits nodes in exactly the order the recursion creates them — helper consumes one element per node, in order. Recognising that the pointer never needs to move backwards is the insight.

Postorder builds the right subtree first

Postorder is left, right, root. Read backwards it is root, right, left. So if you consume postorder from the end, you must construct the right child before the left:

build_in_post.py

def build_tree(inorder, postorder):
    index = {v: i for i, v in enumerate(inorder)}
    post = len(postorder) - 1          # consume from the END
 
    def helper(left, right):
        nonlocal post
        if left > right:
            return None
        root_val = postorder[post]
        post -= 1
        node = TreeNode(root_val)
        mid = index[root_val]
        node.right = helper(mid + 1, right)   # RIGHT before LEFT
        node.left = helper(left, mid - 1)
        return node
 
    return helper(0, len(inorder) - 1)

Building left first here silently produces a mirrored, wrong tree — the code runs, returns a tree of the right size, and fails the tests. It is the defining mistake of LC 106.

Dry run

LC 105 — preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]. The index map is {9:0, 3:1, 15:2, 20:3, 7:4}, and pre starts at 0. Each row is one helper call, indented by recursion depth.

depth	in-order window	preorder[pre]	mid	pre after	result
0	[0,4]	3	1	1	root 3; left gets [0,0], right gets [2,4]
1	[0,0]	9	0	2	node 9
2	[0,-1]	—	—	2	left > right → None
2	[1,0]	—	—	2	None — 9 is a leaf
1	[2,4]	20	3	3	node 20; left [2,2], right [4,4]
2	[2,2]	15	2	4	node 15, both children empty
2	[4,4]	7	4	5	node 7, both children empty

Built tree: [3, 9, 20, null, null, 15, 7]. ✓

Four things to take from that table:

• pre only ever moves forward, and it advances exactly once per node — 5 nodes, pre ends at 5. The empty windows consume nothing. That is the invariant which makes a shared pointer correct: pre-order produces nodes in the same order the recursion creates them, so there is never a reason to look back.
• The windows are in-order indices, not pre-order indices. helper(left, right) never indexes preorder by anything but pre. Mixing the two index spaces is the most common way this template goes wrong.
• left > right is the base case, not left == right. Notice the two “windows” [0,-1] and [1,0]: both are empty, both are reached, and both would be out-of-bounds errors under any other test. A single-element window like [2,2] is not empty — it is a leaf.
• The order of the two recursive calls is forced. node.left must be built first, because the next pre-order element belongs to the left subtree. Swap the two lines and the tree comes out mirrored — with the right size, so the code runs and the tests fail. That is the same trap, inverted, as post-order’s right-before-left.

Complexity

Approach	Time	Space
Index map + shared pointer	$O(n)$	$O(n)$ for the map, $O(h)$ recursion
inorder.index(root) per node	$O(n^2)$	$O(h)$
Array slicing per call	$O(n^2)$	$O(n^2)$ — every level copies
From a rule, e.g. LC 654 max tree	$O(n^2)$ naive, $O(n)$ with a monotonic stack	$O(n)$

The map is the whole difference. inorder.index(v) is an $O(n)$ scan per node, so a degenerate tree with $n = 3000$ costs about nine million comparisons instead of three thousand dictionary lookups. Slicing is worse still, because it also allocates: each of the $h$ levels copies $O(n)$ elements.

The map assumes distinct values

{value: position} is ambiguous the moment a value repeats — and with duplicates, reconstruction from two traversals is not unique anyway, so there is nothing to fix in the code. LC 105 and LC 106 both guarantee distinct values. If asked what happens without that guarantee, the answer is that the problem becomes ill-posed, not that the algorithm needs patching.

Construction from a rule

Some problems define the tree by a property rather than a traversal. LC 654 builds a maximum binary tree: the root is the largest element, and the left and right subtrees are built recursively from the elements on either side.

The naive recursion finds the maximum in each range — $O(n^2)$. A monotonic stack does it in $O(n)$:

max_binary_tree.py

def construct_maximum_binary_tree(nums):
    stack = []                        # values strictly decreasing
    for n in nums:
        node = TreeNode(n)
        while stack and stack[-1].val < n:
            node.left = stack.pop()   # everything smaller becomes our left subtree
        if stack:
            stack[-1].right = node    # we hang off the nearest larger element
        stack.append(node)
    return stack[0]                   # the bottom of the stack is the global max

Each node is pushed once and popped at most once, so it is $O(n)$. The stack bottom ends up holding the largest value — the root.

Approach	Time	Space
Slicing recursion	$O(n^2)$	$O(n^2)$
Index map + shared pointer	$O(n)$	$O(n)$
Find-the-max recursion (654)	$O(n^2)$	$O(n)$
Monotonic stack (654)	$O(n)$	$O(n)$

The variant map

Variant	The root comes from	The split comes from	Problem
Preorder + inorder	Front of preorder	Inorder position	105
Inorder + postorder	Back of postorder	Inorder position	106
Preorder + postorder	Front of preorder	Postorder (full trees only)	889
Preorder of a BST	Front of preorder	Sort it to get inorder, or use bounds	1008
Sorted array	The middle element	Array halves	108
Maximum rule	The largest element	Monotonic stack	654
Serialised string	The token stream	Explicit null markers	297

Practice — real LeetCode problems

LC 105 — Construct Binary Tree from Preorder and Inorder Traversal · Medium

Problem. Given preorder and inorder traversals of a binary tree with distinct values, construct and return the tree.

Constraints. 1 <= len(preorder) <= 3000, both traversals are of the same tree, all values distinct.

Examples. preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] gives the tree [3,9,20,null,null,15,7] · preorder = [-1], inorder = [-1] gives [-1]

Why this test prints level order

The problem returns a tree, so the test serialises your result back into LeetCode’s level-order list form (with trailing nulls trimmed) using a provided level_order helper — letting it compare the whole structure, not just a root value.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Preorder gives the root; inorder tells you how many nodes fall in the left subtree. Recurse on the inorder window and let the preorder pointer advance naturally.

Time $O(n)$. Space $O(n)$ for the map plus $O(h)$ recursion.

Why the shared pointer works: helper consumes exactly one preorder element per node created, and it creates nodes in preorder order (root, then the whole left subtree, then the whole right). So the pointer never needs to jump — it just walks forward.

[1,2,3] / [3,2,1] is a good check: preorder root 1, and inorder puts everything before it, so 1 has only a left child. The result is a left-leaning chain, [1, 2, None, 3] in level order.

Follow-ups you should expect:

• “What if values could repeat?” The index map becomes ambiguous and the tree is not uniquely determined. You would need to pass explicit ranges and potentially backtrack.
• “Preorder + postorder (LC 889)?” Insufficient in general — only unique for full binary trees (every node has 0 or 2 children), because without inorder there is no way to tell a lone child’s side.
• “Iteratively?” Possible with an explicit stack: push nodes as you consume preorder, popping when the top matches the current inorder element. Harder to get right; know it exists.
• “Do it without the index map?” $O(n^2)$; state the trade-off.

LC 106 — Construct Binary Tree from Inorder and Postorder Traversal · Medium

Problem. Given inorder and postorder traversals of a binary tree with distinct values, construct and return the tree.

Constraints. 1 <= len(inorder) <= 3000, both of the same tree, distinct values.

Examples. inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] gives [3,9,20,null,null,15,7]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Identical to LC 105 with two changes: the root comes from the end of postorder, and the recursion builds right before left.

Time $O(n)$. Space $O(n)$.

The ordering is the whole lesson. Postorder is left, right, root; walking it backwards yields root, right, left. Since the pointer moves strictly backwards, the recursion must ask for the right subtree first — otherwise the pointer hands left-subtree values to the right subtree and you get a mirrored tree.

That failure mode is nasty precisely because it is plausible: the tree has the correct node count and a valid shape, so only a value-by-value comparison reveals it. If your LC 106 output looks like a reflection of the expected answer, this is the line to check.

[3,2,1] / [3,2,1] is worth tracing: postorder’s last element 1 is the root; inorder places 3 and 2 before it, so both are in the left subtree, giving the left-leaning chain [1, 2, None, 3].

Follow-ups you should expect: “Why right before left?” — the likeliest question; answer with the reversed-postorder observation. “Could you reverse postorder and reuse the LC 105 code?” — yes, with mirrored child assignment; some find that clearer. “Preorder + postorder?” — LC 889, full trees only. “Construct a BST from preorder alone (LC 1008)?” — sorting gives inorder, or better, recurse with (low, high) bounds in $O(n)$.

LC 654 — Maximum Binary Tree · Medium

Problem. Build a maximum binary tree from nums: the root is the maximum element; its left subtree is built from the elements to the left of that maximum, its right subtree from the elements to the right. Recurse.

Constraints. 1 <= len(nums) <= 1000, 0 <= nums[i] <= 1000, all values unique.

Examples. [3,2,1,6,0,5] gives [6,3,5,null,2,0,null,null,1] · [3,2,1] gives [3,null,2,null,1]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Start with the naive solution and say it: find the maximum in the range, make it the root, recurse on both halves. $O(n^2)$ worst case (a sorted array), and accepted at n <= 1000.

The $O(n)$ solution uses a decreasing monotonic stack. The invariant: the stack holds the right spine of the tree built so far, values decreasing from bottom to top.

When a new value n arrives:

• Every stacked value smaller than n must end up in n’s left subtree, because n is larger and appears later — so it becomes their ancestor. Popping them in order leaves the largest of them as n’s left child.
• If a larger value remains on the stack, n sits to its right and is later, so n becomes that node’s right child (replacing whatever was there — correctly, since the replaced subtree has just been absorbed into n’s left).

Time $O(n)$ — each node pushed once, popped at most once. Space $O(n)$.

[1,2,3] giving [3,2,None,1] is a useful trace: each new value is larger, so each pops the previous and takes it as a left child, ending with root 3.

Follow-ups you should expect: “Why is the stack bottom the root?” — nothing ever pops it, because no later value exceeds the global maximum. “Minimum binary tree instead?” — flip the comparison to an increasing stack. “What if values repeated?” — the tree is no longer uniquely defined; you must specify a tie-break. “Maximum Binary Tree II (LC 998)?” — insert a value appended to the original array by walking the right spine, which is the same invariant.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1008 is the elegant one

Construct BST from Preorder looks like it needs the inorder too — and you could sort the preorder to get it, then run LC 105 in $O(n \log n)$.

But a BST’s ordering already encodes the split. Walk the preorder once, carrying a (low, high) bound: consume the next value only if it fits the current bounds, otherwise return and let an ancestor claim it.

python

def bstFromPreorder(preorder):
    self.i = 0
    def build(low, high):
        if self.i == len(preorder) or not (low < preorder[self.i] < high):
            return None
        val = preorder[self.i]; self.i += 1
        node = TreeNode(val)
        node.left = build(low, val)
        node.right = build(val, high)
        return node
    return build(float("-inf"), float("inf"))

$O(n)$, no sorting, no index map. It is the same bounds idea as validating a BST in BST Patterns — used to build rather than to check.

5 problems

0 easy5 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○105Construct Binary Tree from Preorder and Inorder TraversalmediumIndex map + one advancing pointer; left before rightNeetCode 150Blind 75LeetCode Top Interview 150
• ○106Construct Binary Tree from Inorder and Postorder TraversalmediumConsume postorder backwards; **right before left**LeetCode Top Interview 150
• ○654Maximum Binary TreemediumMonotonic stack for $O(n)$ instead of $O(n^2)$
• ○889Construct Binary Tree from Preorder and Postorder TraversalmediumOnly unique for **full** trees -- no inorder means no split point
• ○1008Construct Binary Search Tree from Preorder TraversalmediumFor a BST, preorder alone suffices -- recurse with `(low, high)` bounds

Interview follow-ups

They ask	What they’re checking	The answer
“Why isn’t one traversal enough?”	Foundations	It records roots but not sides — [1,2] preorder fits two different trees
“Which pairs are sufficient?”	Precision	pre+in and post+in always; pre+post only for full trees; a BST’s preorder alone suffices
“Why the index map?”	Complexity	It replaces an $O(n)$ scan per node, turning $O(n^2)$ into $O(n)$; it needs distinct values
“Why not slice the arrays?”	Hidden costs	Slicing copies, giving $O(n^2)$ time and space
“Why right before left for postorder?”	The key detail	Reversed postorder is root, right, left — building left first mirrors the tree
“What if values repeat?”	Limits	The map is ambiguous and the tree is not uniquely determined
“Can 654 be done in $O(n)$?”	Depth	Yes — a decreasing monotonic stack

Edge-case checklist

• Single node — every template must handle n == 1.
• Left-only chain — preorder [1,2,3], inorder [3,2,1]; also the $O(n^2)$ worst case for the slicing version.
• Right-only chain — the mirror; catches the LC 106 ordering bug.
• Negative values — [-1]; do not assume non-negative anywhere.
• Mismatched traversal lengths — the problems guarantee consistency, but say what you would validate.
• Duplicate values — breaks the index map; know that reconstruction is not unique.
• Sorted input to LC 654 — the naive recursion’s worst case, and where the stack version wins.
• Deep recursion — a 3000-node chain is fine under Python’s 1000-frame limit only if you raise it; worth mentioning.

Self-check

pch.quizTag Tree construction — self-check

1. What does each of the two traversals contribute?

   A Pre-order gives the shape, in-order gives the values B Pre-order tells you which element is the root of each window; in-order tells you how that window splits into left and right subtrees C They are interchangeable D In-order alone is sufficient
   pch.quizShowAnswer

   B — Pre-order tells you which element is the root of each window; in-order tells you how that window splits into left and right subtrees — Roots without sizes, and sizes without roots — neither array alone determines the tree. That is also why serialisation with null markers needs only one traversal: the markers supply the missing structure instead.

2. Why is one shared, ever-advancing `pre` pointer correct?

   A Because the arrays are sorted B Because pre-order produces nodes in exactly the order the recursion creates them — one element consumed per node, never a reason to look backwards C Because the tree is balanced D It is not correct; each call needs its own index
   pch.quizShowAnswer

   B — Because pre-order produces nodes in exactly the order the recursion creates them — one element consumed per node, never a reason to look backwards — In the dry run, pre advances exactly 5 times for 5 nodes and the empty windows consume nothing. Recognising that the pointer never rewinds is what replaces array slicing.

3. What does the index map `{value: inorder position}` buy, and what does it assume?

   A Nothing; it is a micro-optimisation B It turns an O(n) `inorder.index(root)` scan per node into an O(1) lookup, making the build O(n) instead of O(n²) — and it assumes distinct values C It removes the need for recursion D It assumes a balanced tree
   pch.quizShowAnswer

   B — It turns an O(n) `inorder.index(root)` scan per node into an O(1) lookup, making the build O(n) instead of O(n²) — and it assumes distinct values — On a 3000-node degenerate tree that is ~9 million comparisons versus 3000 lookups. With duplicates the map is ambiguous — and reconstruction from two traversals is not unique either, so the problem itself becomes ill-posed.

4. Why is the slicing version O(n²) in space as well as time?

   A Because recursion is O(n²) B Because every level of the recursion copies subarrays of the pre-order and in-order lists, so O(h) levels each allocate O(n) elements C Because the index map is copied D It is not; it is O(n)
   pch.quizShowAnswer

   B — Because every level of the recursion copies subarrays of the pre-order and in-order lists, so O(h) levels each allocate O(n) elements — The slicing version reads beautifully, which is why it is worth knowing why not to write it. It also makes the pre-order slice bounds easy to get wrong.

5. For in-order + post-order (LC 106), why must the right child be built before the left?

   A It does not matter B Because post-order read backwards is root, right, left — so consuming from the end of the array yields the right subtree's root next C Because in-order is reversed too D To keep the pointer moving forward
   pch.quizShowAnswer

   B — Because post-order read backwards is root, right, left — so consuming from the end of the array yields the right subtree's root next — Building left first produces a mirrored tree of the correct size, so it runs and fails the tests silently. It is the defining mistake of LC 106.

6. Why is the base case `left > right` rather than `left == right`?

   A Style B Because a single-element window like [2,2] is a valid leaf, not an empty subtree — and empty windows legitimately arrive as [0,-1] or [1,0], which any other test would mishandle C Because the windows can be negative D To avoid the index map lookup
   pch.quizShowAnswer

   B — Because a single-element window like [2,2] is a valid leaf, not an empty subtree — and empty windows legitimately arrive as [0,-1] or [1,0], which any other test would mishandle — Both out-of-order windows appear in the dry run. Treating left == right as empty would silently drop every leaf.

Recall card

• Cue — “construct the binary tree from these two traversals”, or “build the tree defined by this rule”.
• What each array gives — pre-order (or reversed post-order): the root of each window. In-order: where that root splits the window.
• Template — index = {v: i for i, v in enumerate(inorder)}; one nonlocal pointer into the pre/post array; helper(left, right) over in-order indices.
• Base case — left > right. A single-element window is a leaf, not empty.
• Recursion order is forced — pre-order: left then right; post-order consumed from the end: right then left. Getting it wrong mirrors the tree silently.
• Cost — $O(n)$ with the map, $O(n^2)$ with index() per node, $O(n^2)$ time and space with slicing.
• Assumes distinct values — with duplicates the reconstruction is not unique, so the problem is ill-posed rather than the code being wrong.
• Pre-order + post-order alone is not enough (unless the tree is full) — there is no way to tell a single left child from a single right one.

Recap

• One traversal gives roots; another gives the split. Preorder or postorder supplies the root, inorder supplies the boundary. Neither alone is enough.
• pre+in and post+in always work. pre+post works only for full trees. A BST’s preorder alone works.
• Precompute a value-to-inorder-index map — $O(1)$ lookups instead of $O(n)$ scans, turning $O(n^2)$ into $O(n)$. Requires distinct values.
• Use one advancing pointer, never array slices — slicing costs $O(n^2)$ in both time and space.
• Postorder builds right before left, because reversed postorder is root, right, left. Getting it wrong yields a plausible mirrored tree.
• Rule-based construction (LC 654) often has a monotonic stack solution that beats the obvious $O(n^2)$ recursion.

Next: Serialize, Compare and Subtree — turning trees into strings, and the problems that become easy once you can.