This is particularly important in SQL: Nested set model in SQL, as it is an efficient way to transverse trees there, since querying parents every time would require multiple disk accesses.

The ASCII art visualizations from stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/194031#194031 are worth reproducing.

As a tree:

Root 1
- Child 1.1
  - Child 1.1.1
  - Child 1.1.2
- Child 1.2
  - Child 1.2.1
  - Child 1.2.2

As the sets:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

Consider the following nested set:

0, 8, root
  1, 7, mathematics
    2, 3, geometry
      3, 6, calculus
        4, 5, derivative
        5, 6, integral
      6, 7, algebra
  7, 8, physics

When we want to insert one element, e.g. limit, normally under calculus, we have to specify:

parent
index within parent

so we have a method:

insert(parent, previousSibling)

Tree traversal

1 0

The summary from www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ is a winner:

inorder DFS: 4 2 5 1 3
preorder DFS: 1 2 4 5 3
postorder DFS: 4 5 2 3 1
breadth-first search: 1 2 3 4 5

In principle one could talk about tree traversal of unordered trees as a number of possible traversals without a fixed order. But we won't consider that under this section, only deterministic ordered tree traversals.

Depth-first search

1 0

Pre-order depth-first search (NLR, Preorder DFS)

0 0

This is the order in which you would want to transverse to read the chapters of a book.

Like breadth-first search, this also has the property of visiting parents before any children.

Iterative pre-order

0 0

This is the easiest one to do iteratively:

pop and visit
push right to stack
push left to stack

In-order depth-first search (LNR, Inorder DFS)

0 0

This is the order in which a binary search tree should be traversed for ordered output, i.e.:

everything to the left is smaller than parent
everything to the right is larger than parent

This ordering makes sense for binary trees and not k-ary trees in general because if there are more than two nodes it is not clear what the top node should go in the middle of.

This is unlike pre-order depth-first search and post-order depth-first search which generalize obviously to general trees.