2.2Tree traversals
The idea
Traversals visit every node once; the three depth-first orders differ only in when the root is visited.
Think of it like this: Reading a book: preorder is table of contents first, postorder is summary last, inorder is left page, spine, right page.
Why it exists
Traversal questions are on every paper: read the order or reconstruct the tree.
How it works
- Preorder: root, left, right.
- Inorder: left, root, right (sorted for a BST).
- Postorder: left, right, root.
- Level order uses a queue.
Worked example: BST from 50 30 70 20 40 60 80 35
Inorder: 20 30 35 40 50 60 70 80 (sorted). Preorder: 50 30 20 40 35 70 60 80. Postorder: 20 35 40 30 60 80 70 50.
Now play with it
- →Switch between the four traversals and watch the yellow nodes.
- →Notice the root is first in preorder and last in postorder.
- visit 20
- visit 30
- visit 35
- visit 40
- visit 50
- visit 60
- visit 70
- visit 80
Yellow = already visited. Inorder of this BST is sorted; preorder starts with the root; postorder ends with the root. Preorder + inorder (or postorder + inorder) identify a tree uniquely, preorder + postorder do not.
Check yourself
The inorder traversal of a binary search tree gives
Exam notes (the dense version)
Preorder = root, left, right. Inorder = left, root, right. Postorder = left, right, root. Level order uses a queue. Each is O(n). Inorder of a BST is sorted. Recursive traversal uses O(h) stack space.
Previous year questions: Trees & Binary Search Trees (15)
PYQs are grouped by topic, so this is the full set for Trees & Binary Search Trees; try the ones that match this subtopic. Open all 15 on the topic page.