You have a binary tree. You need to visit every node — but in which order? Preorder? Inorder? Level by level? Each traversal order reveals different information about the tree’s structure, and knowing all four is essential for any serious programmer. Here is the complete guide with working Python code and real output.
In this tutorial you will learn:
- What binary trees are and why traversal order matters
- Four traversal algorithms: Preorder, Inorder, Postorder, Level Order
- How to implement each one in Python with recursion and iteration
- Time and space complexity of each traversal
- Common applications of each traversal type
Page Contents
What Is a Binary Tree?
A binary tree is a hierarchical data structure where each node has at most two children — a left child and a right child. The topmost node is called the root. Nodes with no children are called leaves.
Example Binary Tree (Height = 3, Nodes = 6):
1 ← root
/
2 3 ← level 1
/
4 5 6 ← level 2 (leaves: 4, 5, 6)
Here is the Python class we will use throughout this guide:
class Node:
def __init__(self, val):
self.val = val
self.left = None # left child
self.right = None # right child
# Build the example tree from the diagram above
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)Preorder Traversal: Root → Left → Right
Preorder visits the root first, then the entire left subtree, then the entire right subtree. This is the traversal order you would use to create a copy of the tree or get a prefix expression from an expression tree.
def preorder(node, res=None):
if res is None:
res = []
if node:
res.append(node.val) # Visit root
preorder(node.left, res) # Traverse left
preorder(node.right, res) # Traverse right
return res
# Run it on our tree
result = preorder(root)
print(f"Preorder: {result}")Output
Preorder: [1, 2, 4, 5, 3, 6]The output [1, 2, 4, 5, 3, 6] matches exactly what we expect: root (1) first, then the entire left subtree (2 → 4 → 5), then the right subtree (3 → 6).
Inorder Traversal: Left → Root → Right
Inorder visits the entire left subtree first, then the root, then the right subtree. For a Binary Search Tree (BST), this produces nodes in sorted ascending order. It is also the most common way to get the infix notation of an expression tree.
def inorder(node, res=None):
if res is None:
res = []
if node:
inorder(node.left, res) # Traverse left
res.append(node.val) # Visit root
inorder(node.right, res) # Traverse right
return res
# Run it on our tree
result = inorder(root)
print(f"Inorder: {result}")Output
Inorder: [4, 2, 5, 1, 3, 6]The output [4, 2, 5, 1, 3, 6] shows the left subtree fully explored before the root (1), and the right subtree (3, 6) visited last. For a BST, this is always sorted order.
Postorder Traversal: Left → Right → Root
Postorder visits both subtrees before the root. This is the traversal used to delete a tree (delete children before parent) or to compute postfix notation of expressions.
def postorder(node, res=None):
if res is None:
res = []
if node:
postorder(node.left, res) # Traverse left
postorder(node.right, res) # Traverse right
res.append(node.val) # Visit root
return res
# Run it on our tree
result = postorder(root)
print(f"Postorder: {result}")Output
Postorder: [4, 5, 2, 6, 3, 1]The output [4, 5, 2, 6, 3, 1] confirms both subtrees are fully processed before the root (1) is visited — the root is always last in postorder.
Level Order Traversal: Breadth-First
Level order visits nodes level by level — all nodes at depth 1 before depth 2, and so on. This requires a queue (BFS approach). It is the traversal used to find the shortest path in an unweighted tree and to print a tree level by level.
from collections import deque
def level_order(root):
if not root:
return []
q, result = deque([root]), []
while q:
node = q.popleft()
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
# Run it on our tree
result = level_order(root)
print(f"Level order: {result}")Output
Level order: [1, 2, 3, 4, 5, 6]The output [1, 2, 3, 4, 5, 6] shows level 0 (1) first, then level 1 (2, 3), then level 2 (4, 5, 6) — exactly what we expect for a breadth-first traversal.
Time and Space Complexity
| Traversal | Time | Space | Notes |
|---|---|---|---|
| Preorder | O(n) | O(h) worst case, O(log n) average | h = height of tree; recursive call stack |
| Inorder | O(n) | O(h) worst case, O(log n) average | Same complexity as preorder |
| Postorder | O(n) | O(h) worst case, O(log n) average | Same complexity as preorder |
| Level Order | O(n) | O(w) worst case, O(n/2) average | w = max width of tree; queue holds at most one level |
In all four traversals, every node is visited exactly once — giving O(n) time. The space complexity is dominated by the auxiliary data structure used: the call stack for recursive traversals (depth of tree = height h) and the queue for level order (width of one level). For a balanced tree, height h = O(log n), so average space is O(log n). For a skewed tree (like a linked list), height h = O(n), giving worst-case O(n) space.
Complete Comparison — All Four Traversals Together
from collections import deque
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def preorder(node, res=None):
if res is None:
res = []
if node:
res.append(node.val)
preorder(node.left, res)
preorder(node.right, res)
return res
def inorder(node, res=None):
if res is None:
res = []
if node:
inorder(node.left, res)
res.append(node.val)
inorder(node.right, res)
return res
def postorder(node, res=None):
if res is None:
res = []
if node:
postorder(node.left, res)
postorder(node.right, res)
res.append(node.val)
return res
def level_order(root):
if not root:
return []
q, res = deque([root]), []
while q:
node = q.popleft()
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
# Build the tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
# Run all four traversals
print(f"Preorder: {preorder(root)}")
print(f"Inorder: {inorder(root)}")
print(f"Postorder: {postorder(root)}")
print(f"Level: {level_order(root)}")
# Tree properties
def height(node):
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
def count(node):
if not node:
return 0
return 1 + count(node.left) + count(node.right)
print(f"Height: {height(root)}")
print(f"Total nodes: {count(root)}")Output
Preorder: [1, 2, 4, 5, 3, 6]
Inorder: [4, 2, 5, 1, 3, 6]
Postorder: [4, 5, 2, 6, 3, 1]
Level: [1, 2, 3, 4, 5, 6]
Height: 3
Total nodes: 6Traversal Summary Table
| Traversal | Order | Common Use Case |
|---|---|---|
| Preorder | Root → Left → Right | Copy tree, prefix expression |
| Inorder | Left → Root → Right | Sorted BST output, infix expression |
| Postorder | Left → Right → Root | Delete tree, postfix expression |
| Level Order | Level by level (BFS) | Shortest path, level printing |
Common Mistakes and Gotchas
- Mutable default argument trap — using
res=[]as a default argument in Python is a common bug. The function usesif res is None: res = []to avoid this. Never use a mutable default like[]or{}in function signatures. - Off-by-one in height —
height(node)above returns the number of nodes on the longest path (a leaf gives height 1). Some definitions count edges instead (leaf = height 0). Be consistent in interview answers. - Confusing traversal with tree properties — traversal orders describe how you visit nodes, not the tree’s structure. A “zigzag” or “spiral” order is a variation of level order with alternating direction — not a separate traversal type.
- Iterative inorder without a stack — level order is naturally iterative. Inorder and preorder traversals can also be implemented iteratively using an explicit stack — this is a common interview follow-up question.
Frequently Asked Questions
Can you implement inorder traversal iteratively?
Yes. Use an explicit stack. Push left children until you reach None, then pop, visit the node, and move to its right child. This is a common interview follow-up after the recursive solution.
What happens if the tree is empty (root is None)?
All four traversal functions handle this correctly — they return an empty list [] when root is None. This avoids AttributeError when calling .val on a None node.
Which traversal produces a sorted sequence from a BST?
Inorder traversal on a BST always produces nodes in sorted (ascending) order. This is because a BST’s left subtree contains smaller values, the root is in the middle, and the right subtree contains larger values.
Why is level order called breadth-first search?
Level order explores the tree “widest first” — all nodes at distance 1 from the root before any node at distance 2. This is equivalent to Breadth-First Search (BFS) on a graph where the graph is a tree. Preorder, Inorder, and Postorder are depth-first (DFS) because they go as deep as possible before exploring siblings.
Summary
Binary tree traversals are fundamental to understanding tree-based algorithms. The four traversal orders each serve different purposes:
- Preorder (Root → Left → Right) — tree copying, prefix expressions
- Inorder (Left → Root → Right) — BST sorted output, infix expressions
- Postorder (Left → Right → Root) — deleting trees, postfix expressions
- Level Order (BFS) — shortest path, level-by-level processing
All four traversals run in O(n) time. The recursive versions are cleanest; iterative versions (especially for inorder) are important for interview discussions. Learn more about the binary tree data structure to understand the Node class and tree properties before implementing these traversals, and explore level order traversal in depth with 20+ practice problems.
