What you'll learn
Quick Answer
The three depth-first traversals differ only in when you visit the node relative to its children. Preorder visits the node first, then left, then right — useful for copying a tree. Inorder visits left, node, right, which produces sorted output on a binary search tree. Postorder visits both children before the node, which is what you need for deleting or computing sizes. Level-order visits row by row using a queue rather than recursion.
The Three Traversals Differ by One Line
All three recurse into the left subtree and then the right. The only difference is where the visit happens.
def preorder(node):
if not node: return
visit(node) # <- node FIRST
preorder(node.left)
preorder(node.right)
def inorder(node):
if not node: return
inorder(node.left)
visit(node) # <- node BETWEEN
inorder(node.right)
def postorder(node):
if not node: return
postorder(node.left)
postorder(node.right)
visit(node) # <- node LASTThe names describe where the node sits: pre before the children, in between them, post after. Once you see that, you never have to memorise the orders again.
On this tree:
1
/ \
2 3
/ \
4 5
Preorder: 1 2 4 5 3
Inorder: 4 2 5 1 3
Postorder: 4 5 2 3 1
Level: 1 2 3 4 5All are O(n) time, since each node is visited once, and O(h) space for the call stack where h is the height — O(log n) for a balanced tree, O(n) for a degenerate one.
Why Inorder Matters Most
Inorder has a property the others do not: on a binary search tree it produces the values in sorted order.
That follows directly from the BST rule — everything in the left subtree is smaller, everything in the right is larger. Visiting left, then node, then right therefore emits ascending values.
8
/ \
3 10
/ \ \
1 6 14
Inorder: 1 3 6 8 10 14 ← sortedThis makes inorder the tool for several interview questions:
- Validate a BST. Do an inorder traversal and check the sequence is strictly increasing. Simpler than comparing each node against min and max bounds, though both are valid.
- Find the kth smallest element. Inorder traverse and stop at the kth visit — no need to finish.
- Convert a BST to a sorted list or to a balanced tree.
A common wrong answer to BST validation: checking only that each node's left child is smaller and right child is larger. That is not sufficient — a node deep in the left subtree could still exceed the root. The property must hold against the whole ancestor range, which is exactly what inorder checks for free.
When Preorder and Postorder Are the Right Choice
Preorder processes a node before its children, so use it when the parent must be handled first.
- Copying or serialising a tree. You need the root before you can attach children.
- Printing a directory structure or any hierarchy, where the folder appears above its contents.
- Prefix expression notation.
Postorder processes children before the node, so use it when the node's result depends on its subtrees.
- Deleting a tree. You must free the children before the parent, or you lose the pointers to them.
- Computing height or size. A node's height is one more than the larger child height — you cannot know it until both children are done.
- Calculating directory sizes, where a folder's size is the sum of its contents.
def height(node):
if not node: return 0
left = height(node.left) # children first
right = height(node.right)
return 1 + max(left, right) # then this node — postorder shapeThat function is postorder even though it does not look like a traversal. Recognising the shape is the useful skill: if the answer for a node needs answers from below, it is postorder.
Level-Order Traversal
Level-order is different in kind — it is breadth-first, so it uses a queue rather than recursion.
from collections import deque
def level_order(root):
if not root: return []
result, q = [], deque([root])
while q:
node = q.popleft() # FIFO — this is what makes it level by level
result.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return resultTo group the output by level — a very common interview variant — capture the queue size at the start of each round, since that is exactly how many nodes are on the current level:
while q:
level = []
for _ in range(len(q)): # snapshot the count BEFORE adding children
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
result.append(level)That len(q) snapshot is the trick the question turns on.
Use level-order for the minimum depth of a tree, the right-side view, connecting nodes at the same level, or anything phrased as "level by level". Note its space cost is O(w) where w is the maximum width — for a full binary tree, the last level alone holds half the nodes.
The Iterative Versions Interviewers Ask For
"Now do it without recursion" is a standard follow-up, testing whether you understand that recursion is a stack.
Iterative preorder is the easiest — push right before left, so left is processed first:
def preorder_iterative(root):
if not root: return []
out, stack = [], [root]
while stack:
node = stack.pop()
out.append(node.val)
if node.right: stack.append(node.right) # right first
if node.left: stack.append(node.left) # so left pops first
return outIterative inorder needs you to walk left as far as possible, then backtrack:
def inorder_iterative(root):
out, stack, cur = [], [], root
while cur or stack:
while cur: # go as far left as possible
stack.append(cur)
cur = cur.left
cur = stack.pop() # backtrack
out.append(cur.val)
cur = cur.right # then explore right
return outIterative postorder is the awkward one. The neat trick is to do a modified preorder visiting node, right, left, then reverse the result — which gives left, right, node.
Why bother? Because recursion depth is limited. Python raises RecursionError at around 1000 frames, and a skewed tree of 10,000 nodes has depth 10,000. An iterative version uses heap memory instead and handles it. That practical reason is a good thing to state if asked why you would prefer one.