Traversals: DFS and BFS

Why the order matters

A list has one natural order; a tree does not. Different jobs need different orders. To copy a tree you must create a parent before its children. To delete a tree, or to add up folder sizes, you must finish the children before the parent. To print a BST in sorted order you visit the left side, then the node, then the right side. To find the nearest node to the root that matches something, you go level by level. Knowing which order fits which job is a big part of tree interviews.

The three depth-first orders

Depth-first search (DFS) goes as deep as possible down one branch, then backs up and tries the next branch. The three orders differ only in WHEN you record the current node compared with its two subtrees.

def preorder(node, out):
    if node is None:
        return
    out.append(node.val)       # node first
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)       # node in the middle
    inorder(node.right, out)

def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)       # node last

root = build([1, 2, 3, 4, 5, None, 6])
for walk in (preorder, inorder, postorder):
    out = []
    walk(root, out)
    print(walk.__name__, out)
# Output:
# preorder [1, 2, 4, 5, 3, 6]
# inorder [4, 2, 5, 1, 3, 6]
# postorder [4, 5, 2, 6, 3, 1]

Iterative DFS with a stack

Recursion uses the call stack for you. Python stops at about 1,000 nested calls by default (RecursionError), so a skewed tree with 5,000 nodes breaks a recursive walk. Interviewers also like to ask for the iterative version. The idea is to keep your own stack (a Python list with append and pop).

Iterative inorder: go left as far as possible, pushing every node on the way. When you cannot go left, pop a node, record it, and move to its right child. Repeat while there is a current node or the stack is not empty.

def inorder_iterative(root):
    result, stack, node = [], [], root
    while node or stack:
        while node:              # go left as far as possible
            stack.append(node)
            node = node.left
        node = stack.pop()       # the leftmost unvisited node
        result.append(node.val)
        node = node.right        # then its right subtree
    return result

print(inorder_iterative(build([1, 2, 3, 4, 5, None, 6])))   # Output: [4, 2, 5, 1, 3, 6]

Iterative preorder is simpler: push the root; repeatedly pop a node, record it, then push its RIGHT child before its LEFT child, so the left one comes off the stack first. For postorder, one easy trick is to do a "node, right, left" walk the same way and reverse the result at the end, because the reverse of node-right-left is left-right-node.

Level order (BFS) with a queue

Breadth-first search (BFS) visits all nodes at depth 0, then depth 1, then depth 2. A queue (first in, first out) gives exactly that order: take a node from the front, then add its children at the back. Use collections.deque, because popleft() is O(1), while list.pop(0) is O(n).

To return the answer level by level, read the queue length at the start of each round. Exactly that many nodes belong to the current level; their children form the next level.

from collections import deque

def level_order(root):
    if root is None:
        return []
    levels = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):     # only the nodes of this level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

print(level_order(build([1, 2, 3, 4, 5, None, 6])))   # Output: [[1], [2, 3], [4, 5, 6]]

Zigzag level order is a common twist: left to right on level 0, right to left on level 1, and so on. Do a normal level order and reverse every second level (or add to the front of a deque on odd levels).

Time and space

Every traversal visits each node once and does O(1) work there, so all are O(n) time. Space differs. DFS keeps one path on the stack: O(h), which is O(log n) for a balanced tree and O(n) for a skewed one. BFS keeps one level in the queue: O(w), where w is the widest level; the last level of a perfect tree holds about n/2 nodes, so BFS can need O(n) space.

Common mistakes

• Using list.pop(0) as a queue. Each call shifts the whole list, making BFS O(n²). Fix: collections.deque and popleft().
• Reading len(queue) inside the loop condition while adding children, so levels mix. Fix: save the level size before the inner loop, as range(len(queue)) does.
• Pushing left before right in iterative preorder, which visits the right side first. Fix: push right, then left.
• Returning a new list from every recursive call and joining them (left + [val] + right). It works but copies lists again and again; for big trees pass one list down.
• Recursing on a very deep tree in Python. Fix: use the iterative version, or say that sys.setrecursionlimit only moves the limit and can still crash.