Tree Traversal
·
Why Tree Traversal Needs an Order
A binary tree is non-linear: a node can lead to a left subtree and a right subtree. To process every node exactly once, a traversal must specify the order in which nodes are visited.
This page considers depth-first traversal of binary trees. The three main orders differ only in when the current node is visited relative to its left and right subtrees.
The Recursive Traversal Pattern
Each child of a node is the root of another binary tree. This makes recursion a natural fit.
The base case is an empty tree: perform no action. For a non-empty node, recursively process its subtrees and visit the node at the position required by the chosen order.
traverse(node):
if node is empty:
return
// place visit(node) before, between, or after
// traversal calls for the two child subtrees
The empty-tree check is essential because a leaf has empty left and right subtrees.
Inorder, Preorder, and Postorder
Let visit(node) mean any required processing, such as displaying the node value.
| Traversal | Order | Recursive pattern |
|---|---|---|
| Inorder | left subtree, node, right subtree | inorder(left); visit(node); inorder(right) |
| Preorder | node, left subtree, right subtree | visit(node); preorder(left); preorder(right) |
| Postorder | left subtree, right subtree, node | postorder(left); postorder(right); visit(node) |
For the binary tree below, the traversal order is determined by the location of visit(node).
A
/ \
B C
/ \
D E
- Inorder:
D, B, E, A, C - Preorder:
A, B, D, E, C - Postorder:
D, E, B, C, A
For example, preorder visits A first, then completely processes the left subtree rooted at B, and finally processes the right subtree rooted at C.
Cost of Inorder Traversal
For a binary search tree with n nodes, inorder traversal visits each node once:
[ T(n) = O(n) ]
This time complexity is O(n) whether the binary search tree is balanced or unbalanced. The tree shape can change the recursion depth, but every node is still visited once.
Practice: Trace and Write Traversals
-
For the tree below, write its inorder, preorder, and postorder traversals.
8 / \ 3 10 / \ 9 14 -
Complete the recursive preorder procedure by placing the three operations in the correct order:
visit(node),preorder(node.left), andpreorder(node.right). Include the empty-tree base case. -
A binary search tree has
nnodes and is highly unbalanced. What is the time complexity of its inorder traversal? Explain using the number of node visits.
Common Mistakes
- Omitting the empty-tree base case. Recursive calls on missing children must stop without performing an action.
- Using the correct subtree calls but placing
visit(node)in the wrong position. That changes the traversal order. - Treating inorder, preorder, and postorder as different sets of nodes. Each visits every node once; only the order differs.
- Assuming an unbalanced binary search tree makes inorder traversal take more than
O(n)time. It still visits each of thennodes once.
Key Takeaways
- A traversal gives an explicit order for visiting every node of a non-linear binary tree exactly once.
- Recursive traversal stops at an empty subtree.
- Inorder is left-node-right; preorder is node-left-right; postorder is left-right-node.
- Inorder traversal of a binary search tree with
nnodes runs inO(n)time, whether the tree is balanced or unbalanced.
Sources
- Binary Tree Traversal — NPTEL. Accessed 24 September 2026.
- Programming, Data Structures and Algorithms using C — Week 6 Assignment — NPTEL. Accessed 24 September 2026.
- Design and Analysis of Algorithms — Assessments — NPTEL. Accessed 24 September 2026.
Sources
- https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/traversal.htm — archive.nptel.ac.in (Generated candidate citation)
- Programming, Data Structures and Algorithms using C — Week 6 Assignment — NPTEL (Generated candidate citation)
- Design and Analysis of Algorithms — Assessments — NPTEL (Generated candidate citation)