Tree Traversal Patterns Every Coding Interview Tests

Trees show up in a huge share of interviews, and almost every binary tree interview pattern is a thin variation on one of four traversals. Master DFS and BFS over a tree and you'll have a ready answer for path sums, ancestors, level aggregation, and serialization. This guide walks each tree traversal pattern with recursive and iterative Python, then shows the problem shapes they unlock. For the broader catalog, see our 15 LeetCode patterns overview.

Throughout, assume this node definition:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The two families: DFS and BFS

Every traversal is either depth-first (go deep before wide) or breadth-first (go wide before deep). DFS has three orders that differ only in when you process the current node relative to its children. BFS visits the tree one level at a time. Knowing which one a problem wants is half the battle in any tree coding interview.

Order	Visit sequence	Classic use
Preorder	node, left, right	Copy/serialize a tree, root-first work
Inorder	left, node, right	BST in sorted order, Kth smallest
Postorder	left, right, node	Combine subtree results: height, delete, sums
Level-order (BFS)	by depth, top to bottom	Level aggregation, min depth, right-side view

DFS: the three orders

Recursively, all three are three lines — only the position of the "visit" line changes:

def preorder(node, out):
    if not node: return
    out.append(node.val)        # visit BEFORE children
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)        # visit BETWEEN children
    inorder(node.right, out)

def postorder(node, out):
    if not node: return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)        # visit AFTER children

All are O(n) time and O(h) space for the call stack, where h is the tree height — O(log n) for a balanced tree, O(n) for a skewed one.

Iterative DFS (when recursion is banned)

Interviewers sometimes ask for the iterative version to test your grasp of the call stack. Use an explicit stack. For preorder, push the right child first so the left is processed next:

def preorder_iter(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 out

def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                 # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)        # visit on the way back up
        node = node.right
    return out

BFS: level-order traversal

BFS uses a queue. The key trick: capture the level's size before the inner loop so you process exactly one level at a time, even as you enqueue the next level's children.

from collections import deque

def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):     # snapshot this level's size
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

O(n) time, O(w) space where w is the maximum width of the tree — up to O(n) for the bottom level of a full tree.

Common problem shapes

Path sum (root-to-leaf, DFS)

Problem: Does any root-to-leaf path sum to a target? Carry the remaining target down the recursion and check it at a leaf.

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:   # leaf
        return target == root.val
    rest = target - root.val
    return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)

Lowest common ancestor (postorder DFS)

Problem: Find the lowest node that has both p and q as descendants. Recurse into both subtrees; the split point where one target is found on each side is the answer.

def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:        # p and q are on opposite sides
        return root
    return left or right      # both on one side (or neither)

O(n) time, O(h) space. This is a textbook postorder pattern: you combine the results from both children to decide the current node.

Level aggregation: maximum depth (BFS or DFS)

Problem: Return the height of the tree. The recursive postorder version is two lines — the height is one plus the taller subtree.

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Serialize and deserialize (preorder DFS)

Problem: Encode a tree to a string and rebuild it. A preorder walk with explicit null markers makes the round trip unambiguous.

def serialize(root):
    out = []
    def dfs(node):
        if not node:
            out.append('#')          # null marker
            return
        out.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ','.join(out)

def deserialize(data):
    vals = iter(data.split(','))
    def build():
        v = next(vals)
        if v == '#':
            return None
        node = TreeNode(int(v))
        node.left = build()
        node.right = build()
        return node
    return build()

Both directions are O(n). The null markers are what let you reconstruct the exact shape; skipping them is the most common bug here.

Why inorder is special for BSTs

An inorder traversal of a binary search tree visits nodes in sorted ascending order. That one fact reduces several questions to a single walk: validate a BST by checking the inorder sequence is strictly increasing, find the Kth smallest by stopping the inorder walk after K visits, and convert a BST to a sorted list directly. When you see "BST" and "Kth" or "validate," reach for inorder first.

Common pitfalls

• Missing the null base case. Every recursive helper must return on None first, or you'll hit an AttributeError on a leaf's child.
• Wrong push order in iterative DFS. For preorder, push the right child before the left so the left is processed first — flip it and the output reverses.
• Letting BFS levels blur. Snapshot len(q) before the inner loop; reading it live mixes the current and next levels.
• Confusing height with depth. Height counts edges from a node down to its deepest leaf; depth counts from the root down. Be sure which the problem wants.

FAQ

What are the main tree traversal patterns?

Depth-first search (DFS) in three orders - preorder (node, left, right), inorder (left, node, right), and postorder (left, right, node) - plus breadth-first search (BFS), also called level-order, which visits the tree one level at a time. Almost every binary-tree interview question is a variation of one of these four.

When should I use DFS vs BFS on a tree?

Use DFS when the answer depends on a root-to-leaf path or on combining results from subtrees - path sum, lowest common ancestor, tree height, validation. Use BFS when the answer depends on depth or on processing nodes level by level - level-order output, minimum depth, right-side view, or the shortest number of edges.

Why does inorder traversal matter for binary search trees?

An inorder traversal of a binary search tree visits nodes in sorted ascending order. That single fact powers many questions: validating a BST, finding the Kth smallest element, and converting a BST to a sorted list all reduce to checking or walking the inorder sequence.

What is the time and space complexity of tree traversal?

Every traversal visits each node once, so time is O(n). Space is O(h) for recursive DFS, where h is the tree height (O(log n) balanced, O(n) skewed), because of the call stack. BFS space is O(w), the maximum width of the tree, which can be up to O(n) for the bottom level.

What is the most common tree traversal mistake?

Forgetting the null base case, which causes an AttributeError, and mishandling the recursion-to-iteration conversion - for example, pushing children in the wrong order onto the stack so the output is reversed. For BFS, capturing the level size before the inner loop is essential, otherwise the queue grows mid-iteration and levels blur together.