Introduction
Tree traversal is the process of visiting every node in a tree exactly once in a systematic order. There are two broad families: depth-first traversals (inorder, preorder, postorder), which recursively explore as far as possible along each branch before backtracking, and breadth-first traversal (level-order), which visits nodes level by level using a queue. The choice of traversal matters: inorder traversal of a BST yields sorted output, preorder is useful for copying/serializing a tree, postorder is used for safely deleting a tree or evaluating expression trees, and level-order is used for shortest-path-style processing and printing a tree level by level.
Cricket analogy: Visiting every player in a squad hierarchy is like a tree traversal: depth-first drills go deep into one fielding unit before backtracking, while level-order calls out players row by row on the team photo, useful for printing the squad list rank by rank.
Structure/Syntax
from collections import deque
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.value)
inorder(node.right, out)
def preorder(node, out):
if node:
out.append(node.value)
preorder(node.left, out)
preorder(node.right, out)
def postorder(node, out):
if node:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.value)
def level_order(root):
if root is None:
return []
result, queue = [], deque([root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return resultExplanation
Inorder visits left subtree, then the node, then right subtree (Left-Node-Right) — on a BST this always produces values in ascending sorted order. Preorder visits the node first, then left, then right (Node-Left-Right) — useful for creating a copy of the tree because you record the root before its children. Postorder visits left, then right, then the node (Left-Right-Node) — useful for deleting a tree bottom-up or evaluating an expression tree, since children are fully processed before their parent. Level-order (breadth-first) uses a queue instead of recursion: it processes the root, then enqueues its children, and repeats, visiting the tree level by level, left to right.
Cricket analogy: Inorder (left-node-right) walking a BST of player rankings yields them sorted ascending, like reading a batting average list low to high; preorder records the captain before the squad, useful for copying a team sheet; postorder finalizes support staff before the captain, useful for disbanding a squad; level-order calls out the whole XI row by row using a queue.
Example
# 5
# / \
# 3 8
# / \ \
# 1 4 9
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.right = TreeNode(9)
result = []
inorder(root, result)
print("inorder:", result)
result = []
preorder(root, result)
print("preorder:", result)
result = []
postorder(root, result)
print("postorder:", result)
print("level-order:", level_order(root))Output
For the tree shown above, the traversals produce: inorder -> [1, 3, 4, 5, 8, 9] (sorted, since this is a BST); preorder -> [5, 3, 1, 4, 8, 9] (root first, then left subtree, then right subtree); postorder -> [1, 4, 3, 9, 8, 5] (children before parent, root last); level-order -> [5, 3, 8, 1, 4, 9] (visited level by level, top to bottom, left to right). Each depth-first traversal runs in O(n) time and O(h) space (recursion stack), while level-order also runs in O(n) time but uses O(w) space where w is the maximum width of the tree (up to O(n) for a wide tree).
Cricket analogy: For a squad-ranking tree, inorder gives sorted batting averages, preorder gives captain-first order, postorder gives support-staff-first order, and level-order gives row-by-row squad photo order; each depth-first walk takes O(n) time and O(h) stack space for the squad depth h, while level-order takes O(n) time and O(w) space for the widest row w.
Key Takeaways
- Inorder (Left-Node-Right) yields sorted output on a BST.
- Preorder (Node-Left-Right) is ideal for copying or serializing a tree.
- Postorder (Left-Right-Node) is ideal for safe deletion or expression evaluation.
- Level-order (breadth-first) uses a queue and visits nodes top-to-bottom, left-to-right.
- All traversals are O(n) time; DFS uses O(h) space, BFS uses up to O(n) space.
Practice what you learned
1. Which traversal order visits a BST's nodes in sorted ascending order?
2. Which data structure is typically used to implement level-order (breadth-first) traversal?
3. For the tree with root 5, left child 3, right child 8 (and 3 has children 1, 4; 8 has right child 9), what is the postorder traversal?
4. What is the space complexity of a recursive preorder traversal in the worst case (a completely skewed tree)?
Was this page helpful?
You May Also Like
Binary Trees
A hierarchical data structure where each node has at most two children, forming the foundation for many advanced tree structures.
Binary Search Trees
A binary tree variant that maintains an ordering invariant, enabling fast search, insert, and delete operations.
Graph Traversal: BFS and DFS
Master Breadth-First Search and Depth-First Search, the two fundamental algorithms for exploring graphs.