Tree Traversal

To traverse a data structure is to visit, or read, all of the structure's elements. In a linear data structure like an array, there are two traversal approaches:

1. First to last (called forward-linear traversal), or
2. last to first (backward-linear traversal).

Data structures like binary trees, however, are non-linear. And because they're non-linear, they have several traversal approaches:

1. Depth-first search (DFS) — traversing the tree by starting at the root, and exploring as far as possible along each branch before backtracing.

2. Breadth-first search (BFS) — traversing the tree by starting at the root, and exploring all nodes at the present level before moving to nodes at a subsequent level.

Both approaches have several sub-approaches:

1. Depth-first search:
   1. preorder traversal
   2. inorder traversal
   3. postorder traversal
2. Bread-first search:
   1. level/generational traversal and variations

We examine each of these traversal approaches in turn.