Tree traversal

O(n)

Recursively (or with an explicit queue/stack) visit every node of a tree in a defined order, combining or collecting values along the way.

Signals

binary tree given as a root node with left/right pointersvisit every node (preorder / inorder / postorder / level-order)compute a depth, height, or sum over the whole treeprocess children before or after the parentlevel-by-level output (BFS with a queue)

Template

function traverse(node, result = []) {
    if (!node) return result; // base case
    traverse(node.left, result);
    result.push(node.val); // inorder here; move this line for pre/post
    traverse(node.right, result);
    return result;
}

Looks similar, isn't

Graph BFS/DFS: A tree has no cycles and each node has exactly one parent, so a plain recursive or queue-based walk never revisits a node and needs no visited set. A general graph can have cycles and multiple parents, so BFS/DFS there must track visited nodes.

n nodes, each visited exactly once -> O(n) time. Recursive depth is O(h) (or an explicit O(n) queue for level-order), and h can reach n on a skewed tree.

Learn this pattern