Tree and Graph Traversals

Storing data in a tree or a graph is only half the job; a program must also be able to visit the stored items in a systematic order. Visiting every node exactly once is called a traversal, and the order in which nodes are visited determines what the traversal is useful for. This lesson covers the three classic depth-based tree traversals and the two general strategies, depth-first and breadth-first, that also apply to graphs.

The three binary tree traversals

For a binary tree the three standard traversals differ only in when the current node is processed relative to its left and right subtrees. All three are naturally expressed with recursion, a function that calls itself on the subtrees.

Pre-order visits the node first, then its left subtree, then its right subtree (Node, Left, Right):

PR