DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).
Tree Traversals: three orders, one rule
The most-tested skill in the tree topic — and it reduces to a single question asked at every node.
All three traversals visit every node exactly once and differ only in when the root is handled relative to its subtrees. Learn it as one rule with three positions rather than as three separate procedures.
At every node, do three things in some order:
L = traverse the left subtree
N = visit this node
R = traverse the right subtree
Pre-order N L R root first
In-order L N R root in the middle
Post-order L R N root last
The left subtree is always handled before the right.
Only the position of N changes.
In-order traversal of a binary search tree always produces the values in sorted order. That is not a coincidence to memorise: the BST rule says everything left of a node is smaller and everything right is larger, so visiting left-then-node-then-right visits them smallest-first by construction. If an in-order traversal comes out unsorted, the tree is not a valid BST — which is exactly how you check one.
What each order is actually for
Pre-order handles a node before its children, so it is what you use to copy a tree — the parent must exist before anything can be attached to it. It is also the natural order for writing a tree out to a file.
Post-order handles children before the node, so it is what you use to delete a tree — freeing a parent before its children would lose the pointers to them. The same reasoning applies to evaluating an expression tree: operands before the operator.
In-order gives sorted output for a BST, which covers most of what it is used for.
Reconstructing a tree from two traversals
A favourite exam question, and it follows directly from the rule above.
Given pre-order 5, 3, 1, 4, 8, 9
in-order 1, 3, 4, 5, 8, 9
Step 1: pre-order's FIRST element is the root → 5
Step 2: find 5 in the in-order list
1, 3, 4 | 5 | 8, 9
everything left of it is the left subtree,
everything right of it is the right subtree
Step 3: repeat on each side, taking the next
unused pre-order element as that subtree's root
→ 3 roots the left subtree (1, 4 beneath it)
→ 8 roots the right subtree (9 to its right)
💡 The pairing matters. Pre-order + in-order works, and post-order + in-order works, because in-order is what splits left from right. Pre-order + post-order does NOT uniquely determine a tree — with neither one able to separate the subtrees, several different trees produce the same pair. Examiners ask this specifically.
Commonly confused
Which one is "the" traversal. None. The order is chosen for the task — copy, delete, or sorted output.
In-order and sorted. In-order gives sorted output for a BST. On an arbitrary binary tree it gives no particular order.
Level order. Breadth-first, visiting each depth in turn, and needs a queue rather than recursion — a different mechanism from the three above.
Rapid revision
One rule, three positions for N. Left always before right.
In-order on a BST is sorted — and that is the test for a valid BST.
Pre-order to copy, post-order to delete.
In-order plus one other reconstructs a tree; pre plus post does not.
Syllabus points
Pre-order, in-order, post-order (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Related topics in Data Structure, Lists, Linked Lists and Trees