CODINGNOW
← Back to Algorithm series
🌳
Trees
Pre / In / Post-order Β· Level-order Β· recursive vs iterative

17. Tree Traversal

Four canonical traversals of binary trees: preorder, inorder, postorder, and level-order. Master both the recursive and iterative versions.

treetraversalrecursion
Duration
⏱ ~1 hour
Level
πŸ“Š Intermediate
Prerequisite
🎯 Lecture 14
OUTCOME
Implement all four traversals in 10 lines each, recursive or iterative.

What you'll learn

  • 1Implement preorder, inorder, postorder traversals
  • 2Implement level-order traversal with BFS
  • 3Convert between recursive and iterative forms

Overview

Tree traversals are the foundation of any tree algorithm. Preorder = root first; inorder = root in middle; postorder = root last; level-order = BFS by depth.

Core Concepts

1. Node class

python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. Preorder (root β†’ left β†’ right)

python
def preorder(node):
    if not node: return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

3. Inorder (left β†’ root β†’ right)

python
def inorder(node):
    if not node: return
    inorder(node.left)
    print(node.val)
    inorder(node.right)
# Inorder of a BST gives sorted output.

4. Postorder (left β†’ right β†’ root)

python
def postorder(node):
    if not node: return
    postorder(node.left)
    postorder(node.right)
    print(node.val)
# Postorder is used for deleting trees, computing sizes bottom-up.

5. Level-order (BFS)

python
from collections import deque

def level_order(root):
    if not root: return
    q = deque([root])
    while q:
        u = q.popleft()
        print(u.val)
        if u.left:  q.append(u.left)
        if u.right: q.append(u.right)

6. Iterative inorder (with explicit stack)

python
def inorder_iter(root):
    stack, cur = [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        print(cur.val)
        cur = cur.right

Examples

Example 1 β€” src/01_traversals.py

All four traversals on a sample tree.

Example 2 β€” src/02_iterative.py

Iterative preorder, inorder, postorder.

Example 3 β€” src/03_level_order_layers.py

Level-order that returns nodes grouped by level (list of lists).

Example 4 β€” src/04_reconstruct.py

Reconstruct a tree from inorder + preorder traversals.

Common Mistakes

  1. Recursion limit issues for deep trees β€” bump sys.setrecursionlimit.
  2. Forgetting the base case `if not node: return` β†’ infinite recursion or NoneType error.
  3. Confusing preorder and postorder.
  4. Mixing up left and right children when reading BOJ input.

Recap

  • DFS traversals: pre / in / post β€” order of visiting the root.
  • BFS traversal: level by level with a deque.
  • Inorder of BST = sorted.

Try It

  1. BOJ 1991 (Tree traversal).
  2. BOJ 11725 (Find parent in tree).
Example code / lecture materials

All lecture materials and example code are openly available on GitHub.

View on GitHub β†—