Pointer Walk

Depth-First Tree Traversal

Walking a tree to the bottom before going sideways. The same pattern repeats at every level, smaller each time.

AlgorithmsBeginner8 min read

Visiting every node

A tree stores things in a branching shape: a folder with subfolders, a web page with elements inside elements, an expression with brackets. To do anything with all of it (print it, search it, add it up) you must visit every node exactly once. That is a traversal.

A list has one obvious order. A tree does not. At every node there is a choice of where to go next.

Depth-first: go to the bottom before going sideways

Depth-first traversal follows one branch all the way down, then backs up to the last place it had a choice and takes the other branch.

The whole method is one small recursive function:

python
def walk(node):
    if node is None:
        return
    walk(node.left)
    walk(node.right)

"Walk a tree" means "walk its left part, then walk its right part". Each part is itself a tree, so the same function handles it. The same pattern repeats at every level, on a smaller piece each time.

Depth-first: pre-orderInteractive
DBACFEG

Visited so far

Start. Visit the node, then its left side, then its right side. The same rule is applied again at every node.

Depth right now
0
Calls in progress
–

Watch the "calls in progress" line. It is the path from the top of the tree to where the walk is now. Stepping down adds a call. Finishing a node removes one. This list is the call stack, and it is all the memory a depth-first walk needs: one entry per level, however many nodes there are.

Three orders

Nothing above says when to actually do something with a node. There are three places to put that line, and they give three different orders.

python
def walk(node):
    if node is None:
        return
    # visit(node) here: pre-order
    walk(node.left)
    # visit(node) here: in-order
    walk(node.right)
    # visit(node) here: post-order

The route through the tree is identical in all three. Only the moment of the visit changes.

Depth-first: pre-orderInteractive
Order
DBACFEG

Visited so far

Start. Visit the node, then its left side, then its right side. The same rule is applied again at every node.

Depth right now
0
Calls in progress
–
OrderRuleResult on this treeGood for
Pre-orderNode, left, rightD B A C F E GCopying a tree, printing a folder before its contents
In-orderLeft, node, rightA B C D E F GReading a search tree in sorted order
Post-orderLeft, right, nodeA C B E G F DDeleting a tree, working out folder sizes: children first

Example

Why post-order for folder sizes

The size of a folder is the sum of the sizes of everything inside it. You cannot know a folder's size until you know its subfolders' sizes. So each subfolder must be finished before its parent is visited. That is post-order.

The other way: breadth-first

Depth-first is not the only choice. Breadth-first traversal visits level by level: the root, then all its children, then all their children. It uses a queue of nodes to visit, where depth-first uses the call stack.

Depth-firstBreadth-first
GoesDown a branch, then backs upAcross a level, then the next
RemembersOne path: as deep as the treeOne level: as wide as the tree
Finds firstWhatever is down the first branchWhatever is closest to the root

Use breadth-first when you want the nearest match. Use depth-first when you need to reach the leaves, or when children must be handled before or after their parent.

Key takeaways

  • A traversal visits every node of a tree once.
  • Depth-first goes down one branch fully before trying the next. It is naturally recursive.
  • The call stack holds the path from the root to the current node.
  • Pre-order, in-order and post-order follow the same route and differ only in when the node is visited.
  • In-order reads a search tree in sorted order. Post-order handles children before their parent.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress