Tree traversal is not merely a vocabulary exercise. A traversal turns a branching object into a linear sequence, and reconstruction asks how much of the original branching structure that sequence preserves. The same recursive decomposition—root, left subtree, right subtree—governs both tasks.
This note develops that connection carefully. We first define the three depth-first orders, then prove the recursive procedures correct, and finally reconstruct a tree from preorder plus inorder or postorder plus inorder. The uniqueness claim always carries an essential assumption: node keys are distinct.
Motivation
Suppose a program stores only a list of node keys after visiting a tree. Can a later program recover the exact tree? The answer depends on what the visit order reveals.
- Preorder exposes the root of every nonempty subtree before its descendants.
- Postorder exposes that root after its descendants.
- Inorder places the entire left subtree before the root and the entire right subtree after it.
No one of these observations is normally enough by itself. The useful pairing is that preorder or postorder identifies a root, while inorder identifies the boundary between its two subtrees. Reconstruction is therefore not a trick to memorize; it is repeated use of one recursive invariant.
Definitions
Definition
Binary tree and recursive subtree structure
A binary tree is either empty, or consists of a root node together with an ordered pair of binary trees called its left subtree and right subtree. Either subtree may be empty.
The order matters: exchanging a left and a right child generally produces a different binary tree.
For a nonempty tree, the root has no parent. A node directly below another is its child; nodes reached by repeatedly following child links are descendants. The reverse relation gives ancestors. A leaf has no children, whereas an internal node has at least one child. The subtree rooted at a node contains that node and all of its descendants.
We write h for the number of nodes on a longest root-to-leaf path. Thus a
one-node tree has height 1. This convention makes the later recursion-stack
bound unambiguous.
Definition
Preorder, inorder, and postorder
For a nonempty tree with root R, left subtree L, and right subtree T:
- preorder is
R, then the preorder ofL, then the preorder ofT; - inorder is the inorder of
L, thenR, then the inorder ofT; - postorder is the postorder of
L, then the postorder ofT, thenR.
The traversal of an empty tree is the empty sequence.
The definitions translate directly into recursive pseudocode:
Preorder(node): Inorder(node):
if node is null: return if node is null: return
visit(node) Inorder(node.left)
Preorder(node.left) visit(node)
Preorder(node.right) Inorder(node.right)
Postorder(node):
if node is null: return
Postorder(node.left)
Postorder(node.right)
visit(node)
The position of visit is the only change, but it changes the information
visible at the beginning or end of every subtree segment. Inorder is not a
sorting operation: it produces increasing keys only when the tree also
satisfies the binary-search-tree invariant, which is studied in the next note.
It is useful to state exactly what each sequence preserves. Within a subtree whose boundaries are already known, preorder makes its first entry the root, whereas postorder makes its last entry the root. Inorder preserves the fact that all entries before a known root belong to its left subtree and all entries after it belong to its right subtree. It does not, by itself, identify that root. None of the three sequences records explicit null-child markers in the form used here. This explains both sides of the reconstruction result: a root-revealing order and inorder complement one another, while a missing boundary or missing root choice leaves room for several shapes.
The word “within” is important. A consecutive traversal segment represents a subtree only after the recursive algorithm has established its boundaries. One may not choose an arbitrary interval from the full sequence and assume it is a subtree.
Theorem/Proposition
Theorem
Recursive traversal invariant
When any one of the three procedures is called on a subtree, it visits every node of that subtree exactly once, visits no node outside it, and emits the subtree's nodes in the order stated by that traversal's recursive definition.
Theorem
Unique reconstruction from inorder and a root-revealing order
Let all node keys be distinct. If two compatible sequences are the preorder and inorder traversals of a binary tree, they determine exactly one ordered binary tree. The same statement holds for postorder together with inorder.
Theorem
A single inorder sequence is insufficient
Even with distinct keys, inorder alone does not in general determine the root, the parent-child relations, or the shape of a binary tree.
The word compatible matters. The two inputs must have the same length and the same key set, and every recursively chosen root must lie inside the active inorder interval. Otherwise the inputs describe no common tree.
Proof sketch or proof idea
For traversal correctness, use induction on the number of nodes in the input subtree. The empty-tree call returns immediately, so the claim is true. For a nonempty subtree, the recursive calls satisfy the claim for the strictly smaller left and right subtrees. The procedure visits the root once and places that visit before, between, or after those two correct recursive outputs. Consequently every node appears exactly once in the required order.
For reconstruction from preorder and inorder, let P and I denote the
active sequence segments. The first key of P must be the root r. Because
keys are distinct, r has one position in I. Everything before r in I
belongs to the left subtree; everything after it belongs to the right subtree.
Those two lengths split the remainder of P into its left and right preorder
segments. The same argument applies recursively. Induction on the segment
length proves both existence for compatible inputs and uniqueness.
For postorder and inorder, the last key of the active postorder segment is the
root. Inorder again fixes the left and right sizes. A postorder segment has the
form left, right, root, so those sizes determine its two child segments, and
the induction repeats.
Distinctness is not a cosmetic condition. With duplicate keys, a root value may occur in several inorder positions, so “find the root in inorder” no longer determines one split. Reconstruction then needs extra identity information—such as uniquely labelled occurrences—or an explicit duplicate policy; raw repeated values are insufficient for the theorem above.
The insufficiency proposition follows from a counterexample. Both trees below
have inorder (B, A, C):
A C
/ \ /
B C A
/
B
The sequence fixes the left-to-right order but does not say which key is the
root. Similarly, preorder (A, B) and postorder (B, A) describe either a
left child B or a right child B. Thus preorder plus postorder is also
insufficient for arbitrary binary trees unless additional structural
conditions are supplied.
Worked examples
Worked example
Tracing all three orders on one tree
Consider the following tree from the course traversal example:
A
/ \
B C
/ / \
D E F
\ / \
G H J
Apply the recursive rule separately at every subtree:
- preorder:
A, B, D, C, E, G, F, H, J; - inorder:
D, B, A, E, G, C, H, F, J; - postorder:
D, B, G, E, H, J, F, C, A.
For example, the subtree rooted at C contributes C,E,G,F,H,J to preorder,
E,G,C,H,F,J to inorder, and G,E,H,J,F,C to postorder. Treating it as a
smaller instance prevents nodes from drifting into the wrong order.
Worked example
Reconstruction from preorder and inorder
Use the preorder and inorder sequences above. Preorder begins with A, so A
is the root. In inorder,
D,B | A | E,G,C,H,F,J,
so the left subtree has two nodes. The next two preorder keys, B,D, must form
that left subtree; the remaining keys C,E,G,F,H,J form the right subtree.
For the left part, B is the preorder root and D | B shows that D is its
left child. For the right part, C is the root and
E,G | C | H,F,J fixes a two-node left subtree and a three-node right
subtree. Repeating the split gives E with right child G, and F with left
child H and right child J. The original tree is recovered.
With inclusive array bounds and a key-to-inorder-position map, the core procedure is:
BuildPre(preLo, preHi, inLo, inHi):
if preLo > preHi or inLo > inHi:
require preLo > preHi and inLo > inHi
return null
rootKey = preorder[preLo]
k = inorderPosition[rootKey]
require inLo <= k <= inHi
leftSize = k - inLo
node = new Node(rootKey)
node.left = BuildPre(preLo + 1, preLo + leftSize,
inLo, k - 1)
node.right = BuildPre(preLo + leftSize + 1, preHi,
k + 1, inHi)
return node
Worked example
Reconstruction from postorder and inorder
Now use postorder D,B,G,E,H,J,F,C,A with the same inorder sequence. The last
postorder key A is the root. The inorder split again gives two left-subtree
nodes and six right-subtree nodes, so postorder splits as
D,B | G,E,H,J,F,C | A.
The right segment ends in C. Its inorder split is
E,G | C | H,F,J, so its postorder child segments are G,E and H,J,F.
This yields E with right child G, and F with children H and J.
BuildPost(postLo, postHi, inLo, inHi):
if postLo > postHi or inLo > inHi:
require postLo > postHi and inLo > inHi
return null
rootKey = postorder[postHi]
k = inorderPosition[rootKey]
require inLo <= k <= inHi
leftSize = k - inLo
node = new Node(rootKey)
node.left = BuildPost(postLo, postLo + leftSize - 1,
inLo, k - 1)
node.right = BuildPost(postLo + leftSize, postHi - 1,
k + 1, inHi)
return node
This range-based version may build either child first. A different
implementation that consumes postorder backward through one shared cursor
must build the right subtree first, because the reversed order is
root, right, left.
Worked example
Detecting incompatible inputs before inventing a tree
Suppose preorder is (A, B, C) but inorder is (B, A, D). The key sets differ,
so no binary tree can have both traversals. As another failure, if an active
preorder root is found in the global inorder list but outside the current
inorder interval, the proposed parent-child split contradicts an earlier
choice. A robust implementation rejects either input instead of silently
returning a partial tree.
Complexity
Assuming visit does constant local work, every traversal processes each of
n nodes once, so its time is Theta(n). The recursive call stack uses
O(h) space: it is O(log n) when the tree height is logarithmic in n, and
O(n) for a completely skewed tree. Storing the emitted sequence itself
requires Theta(n) additional output space.
For reconstruction, repeatedly scanning the active inorder segment to locate
each root can cost Theta(n^2) on a skewed input. Instead, validate the key
sets once, build a map from each distinct key to its inorder index in
Theta(n) time, and pass index ranges rather than copying subarrays. Assuming
constant-time map lookup, every node is then created once, giving Theta(n)
time. The map uses Theta(n) auxiliary space and recursion uses O(h); the
returned tree itself necessarily uses Theta(n) space.
Common mistakes
Common mistake
Treating inorder as sorted for every binary tree
Inorder means left-root-right. It is sorted only when a separate ordering invariant, such as the BST invariant, guarantees that relation among keys.
Common mistake
Using preorder or postorder to guess the split
Preorder and postorder reveal a subtree root, but inorder determines how many nodes belong on each side. Without that split, child boundaries are generally ambiguous.
Common mistake
Forgetting the distinct-key assumption
A value-to-index map is not valid evidence of one root position when the same value occurs more than once. Label occurrences or state a duplicate policy.
Common mistake
Hiding quadratic work inside a recursive algorithm
Scanning inorder or copying slices at every call can make a seemingly simple recursion quadratic. Precompute positions and pass bounds.
Common mistake
Building the wrong child with a backward cursor
When one shared cursor reads postorder from the end, construct right before left. Range-based pseudocode does not have this dependency because both child ranges are computed explicitly.
Summary
- Preorder, inorder, and postorder differ only in when the root is visited, but that timing changes what each sequence reveals.
- Recursive traversal is correct because each call owns exactly one subtree.
- With distinct keys, preorder plus inorder or postorder plus inorder uniquely determines an ordered binary tree.
- Inorder alone—and preorder plus postorder for arbitrary binary trees—can be ambiguous.
- Index maps and range boundaries reduce reconstruction from possible
Theta(n^2)time toTheta(n)under constant-time lookup.
Exercises
Checkpoint
1. A tree has root M; its left child H has right child K; its right child T has left child P. Give preorder, inorder, and postorder.
Apply the same recursive template to each subtree before combining the pieces.
Checkpoint
2. For preorder (M,H,K,T,P) and inorder (H,K,M,P,T), identify the root and the two traversal segments for each child subtree.
Use the root position in inorder and the resulting left-subtree size.
Checkpoint
3. For postorder (K,H,P,T,M) and the same inorder sequence, identify the root and the two postorder child segments.
The root is at the end, and inorder still supplies the child sizes.
Checkpoint
4. Explain why preorder (A,B) and postorder (B,A) do not determine whether B is a left child or a right child.
Construct two ordered binary trees with the same two sequences.
Checkpoint
5. Why can scanning inorder at every recursive call take quadratic time, and what two implementation choices recover linear time?
Consider a skewed tree, then separate root lookup from subarray copying.
Solutions
Solution · 1. Traversal trace
Preorder is M,H,K,T,P; inorder is H,K,M,P,T; postorder is K,H,P,T,M.
For H, the missing left child contributes nothing and K follows H in
preorder but precedes the return to M in the other traversals.
Solution · 2. Preorder and inorder split
The root is M. Inorder splits as H,K | M | P,T, so the left and right
subtree sizes are both two. After consuming preorder's root entry M, the
remaining preorder segment therefore splits as
H,K | T,P. The recursive input pairs are (H,K) with (H,K), and (T,P)
with (P,T).
Solution · 3. Postorder and inorder split
The last key M is the root. The inorder sizes split the preceding postorder
keys as K,H | P,T | M. Thus (K,H) pairs with left inorder (H,K), while
(P,T) pairs with right inorder (P,T).
Solution · 4. Ambiguity
One tree has root A with left child B; the other has root A with right
child B. Both visit A before B in preorder and B before A in
postorder. Neither sequence records the empty side, so the two shapes cannot be
distinguished.
Solution · 5. Complexity repair
In a skewed tree, scans can have lengths n, n-1, ..., 1, whose sum is
Theta(n^2). Build one key-to-inorder-index map so each root position is found
in constant time, and pass integer bounds so recursive calls do not copy
subarrays. Each node is then processed once, for Theta(n) time under the map
assumption.