Depth-first vs breadth-first

There are two fundamental orders for visiting the nodes of a tree. Knowing which to reach for is half the battle.

Depth-first (DFS)

Go deep first: fully explore one branch before backing up to the next. DFS is naturally recursive — visit the node, recurse left, recurse right:

function dfs(node):
    if node is nothing:
        return
    // visit node here  (pre-order)
    dfs(node.left)
    dfs(node.right)

DFS uses the call stack (or an explicit stack). Its memory is O(h), the tree's height. It's the right tool when the answer depends on a path from root to a node — sums, includes, heights, root-to-leaf paths.

Three DFS orders: pre-, in-, post-order

When you visit the node — relative to recursing into its children — gives DFS three named orders:

Order	Visit sequence	Visit the node…
pre-order	node, left, right	before its children
in-order	left, node, right	between its children
post-order	left, right, node	after both children

function traverse(node):
    if node is nothing: return
    // pre-order: visit here
    traverse(node.left)
    // in-order: visit here
    traverse(node.right)
    // post-order: visit here

They visit the same nodes in different sequences. The snippet above is pre-order (visit the node first, before recursing). In-order is special for binary search trees — it yields the values in sorted order. Post-order visits a node only after both subtrees are done, which is what you want when a node's result depends on its children's (heights, deleting a tree, evaluating an expression tree).

Breadth-first (BFS)

Go wide first: visit all nodes at depth 0, then depth 1, then depth 2… BFS uses a queue:

queue = [root]
while queue is not empty:
    node = queue.removeFirst()
    // visit node here
    if node.left exists:  queue.append(node.left)
    if node.right exists: queue.append(node.right)

BFS visits nodes in level order. Its memory is O(w), the maximum width of the tree (up to ~n/2 nodes on the bottom level). It's the right tool for anything "by level" — level averages, the bottom-most value, shortest depth to something.

Choosing

You want…	Use
A property of a root-to-node path	DFS
Anything organised by level/depth	BFS
The shortest number of steps	BFS

Both visit every node once — O(n) time. They differ in order and in which resource (stack depth vs queue width) bounds their memory. The problems ahead let you practise both until the choice is automatic.