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

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

text

  1            1
 /              \
2                2

text

  1            1
 /              \
2                2

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

Adding inorder disambiguates: inorder [2, 1][2, 1] means 22 precedes the root, so it is the left child; inorder [1, 2][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.

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)

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 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:])

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 prepre pointer that only ever advances avoids all of it. It works because preorder visits nodes in exactly the order the recursion creates them — helperhelper 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, rootleft, right, root. Read backwards it is root, right, leftroot, 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)

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.

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

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 preorderpreorder and inorderinorder traversals of a binary tree with distinct values, construct and return the tree.

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

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

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: helperhelper 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][1,2,3] / [3,2,1][3,2,1] is a good check: preorder root 11, and inorder puts everything before it, so 11 has only a left child. The result is a left-leaning chain, [1, 2, None, 3][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 inorderinorder and postorderpostorder traversals of a binary tree with distinct values, construct and return the tree.

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

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

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, rootleft, right, root; walking it backwards yields root, right, leftroot, 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] / [3,2,1][3,2,1] is worth tracing: postorder’s last element 11 is the root; inorder places 33 and 22 before it, so both are in the left subtree, giving the left-leaning chain [1, 2, None, 3][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)(low, high) bounds in $O(n)$ .

LC 654 — Maximum Binary Tree · Medium

Problem. Build a maximum binary tree from numsnums: 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) <= 10001 <= len(nums) <= 1000, 0 <= nums[i] <= 10000 <= nums[i] <= 1000, all values unique.

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

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 <= 1000n <= 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 nn arrives:

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

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

[1,2,3][1,2,3] giving [3,2,None,1][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 33.

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

#	Problem	Difficulty	The twist
108	Convert Sorted Array to Binary Search Tree	Easy	Take the middle as root — balance comes for free
105	Construct Binary Tree from Preorder and Inorder Traversal	Medium	Index map + one advancing pointer; left before right
106	Construct Binary Tree from Inorder and Postorder Traversal	Medium	Consume postorder backwards; right before left
654	Maximum Binary Tree	Medium	Monotonic stack for $O(n)$ instead of $O(n^2)$
889	Construct Binary Tree from Preorder and Postorder Traversal	Medium	Only unique for full trees — no inorder means no split point
1008	Construct Binary Search Tree from Preorder Traversal	Medium	For a BST, preorder alone suffices — recurse with `(low, high)(low, high)` bounds

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)(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"))

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.

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][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 == 1n == 1.
Left-only chain — preorder [1,2,3]preorder [1,2,3], inorder [3,2,1]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][-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.

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, leftroot, 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Tree Construction from Traversals

What you’ll learn

The cue

The template — preorder + inorder

Postorder builds the right subtree first

Construction from a rule

The variant map

Practice — real LeetCode problems

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

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

LC 654 — Maximum Binary Tree · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?