Tree Traversal Interview Patterns: Inorder, Level Order, Zigzag, and Serialize/Deserialize (2025)

The Four Traversals

Binary tree traversals: Inorder (left, root, right) — gives sorted order for a BST. Preorder (root, left, right) — useful for copying a tree, prefix expression. Postorder (left, right, root) — useful for deleting a tree, postfix expression. Level order (BFS) — visits nodes level by level, shortest-path style. Know both recursive and iterative implementations. Recursive is compact; iterative avoids stack overflow on deep trees and is often required in interviews.

def inorder(root):
    result = []
    stack = []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

Level Order Traversal (BFS)

Process nodes level by level using a queue. Track level boundaries by processing the entire current queue size in one loop iteration (snapshotting the current level size).

from collections import deque

def level_order(root):
    if not root: return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):  # process exactly one level
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Variants: LC 103 Zigzag level order — alternate left-to-right and right-to-left. Use a deque: for odd levels append right, for even levels appendleft. LC 116 Populating Next Right Pointers — level order, set node.next for each node to the next node in the same level. LC 513 Find Bottom Left Value — return the first node of the last level.

Path Problems

LC 112 (Path Sum): DFS, subtract node value from remaining target. At leaf: check if remaining == 0. LC 113 (Path Sum II): DFS with a running path list. At leaf with remaining==0: append a copy to results. Pop after recursion (backtrack). LC 124 (Binary Tree Maximum Path Sum): at each node, compute max gain from left subtree and right subtree (max(0, left_gain) to ignore negative paths). Update global max with left_gain + node.val + right_gain. Return node.val + max(left_gain, right_gain) to the parent (can only go one direction in a path from the parent’s perspective). LC 543 (Diameter): same pattern — diameter through a node = left_depth + right_depth.

Lowest Common Ancestor (LC 236, 235)

LC 236 (general binary tree): DFS post-order. If current node == p or q, return it. Recurse left and right. If both return non-null: current node is the LCA. If one returns null: LCA is in the other subtree. LC 235 (BST): if both p and q are less than root, LCA is in left subtree. If both greater, right subtree. Otherwise, root is the LCA. O(h) time. For the general case, the post-order approach uses O(n) time and O(h) space (recursion stack).

Serialize and Deserialize Binary Tree (LC 297)

Preorder serialization: serialize = preorder DFS, write “#” for null. Deserialize: use a global index (or iterator) into the serialized array. At each call: if value is “#”, return None; else create a node and recurse for left and right children.

def serialize(root):
    res = []
    def dfs(node):
        if not node: res.append("#"); return
        res.append(str(node.val))
        dfs(node.left); dfs(node.right)
    dfs(root)
    return ",".join(res)

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

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: LinkedIn Interview Guide

Asked at: Atlassian Interview Guide