Traversal

Process of visiting (performing an action on) each node in a data structure, typically categorized as either breadth-first or depth-first.

Tree Traversal

Trees are traversed from the root breadth-first through level order traversal and depth-first through preorder, inorder, and postorder traversal.

Level Order. Each node in a level is visited in-order before moving onto the next deepest level.
```
// Psuedocode Omitted
```
Preorder. Visit a node, then traverse its left subtree fully, then its right subtree.
```
visit(node)
preOrder(node.left)
preOrder(node.right)
```
Inorder. Traverse a node’s left subtree, visit itself, then traverse its right subtree.
```
inOrder(node.left)
visit(node)
inOrder(node.right)
```

Postorder. Traverse a node’s left subtree, then its right subtree, then visit itself.

postOrder(node.left)
postOrder(node.right)
visit(node)

Graph Traversal

Graphs are traversed from an arbitrary source node breadth-first and depth-first, the latter of which through preorder and postorder traversal. To avoid visiting previously visited nodes, visited nodes are marked. Additionally, for an unweighted graph, visitation order may not be unique if neighbors are chosen arbitrarily.

Breadth-First. Generalization of level order, visits sets of nodes, characterized by the number of edges away from the source node, in order from closest to furthest away.
Preorder. Visit a node, visit all unmarked nodes in a neighbor’s subgraph, then do the same for the other neighbors.
Postorder. Preorder traversal, but any source node is visited last.

One possible order is [3, 4, 7, 6, 8, 5, 2, 1, 0]

Graphs

Graphs can be represented programmatically in the following 3 ways:

Adjacency Matrix. Two nodes, indexed by $i$ and $j$, are adjacent if the entry at position $(i, j)$ in an $V$ by $V$ boolean-valued adjacency matrix is True

$Caveat. Inefficient for sparse graphs, since the matrix itself takes $V^2$ space and visiting nodes adjacent to a single node is $\Theta (V)$.$

Caveat. Inefficient for sparse graphs, since the matrix itself takes $V^2$ space and visiting nodes adjacent to a single node is $\Theta (V)$.
Edge Set. A set stores pairs of indices which represent edges between the nodes indexed by those indices.

$Caveat. Visiting nodes adjacent to a single node is $\Theta(E)$ since adjacencies are not organized efficiently.$

Caveat. Visiting nodes adjacent to a single node is $\Theta(E)$ since adjacencies are not organized efficiently.

Adjacency List. An array stores a list at index $i$ which stores the indices of all nodes adjacent to the node indexed at $i$.

$Caveat. Inefficient for dense graphs, since visiting nodes adjacent to a single node is $\mathcal{\Theta}(V^2)$ (since $E$ is $\Theta(V^2)$).$

Caveat. Inefficient for dense graphs, since visiting nodes adjacent to a single node is $\mathcal{\Theta}(V^2)$ (since $E$ is $\Theta(V^2)$).

In practice, an adjacency list representation is usually opted for over an adjacency matrix representation. This is because search algorithms, like breadth-first (BFS) and depth-first (DFS) search, at worst, need to consider each edge twice (once for each vertex it is incident to, see DepthFirstPaths below).

Doing this with an adjacency matrix implementation requires going through $\Theta(V^2)$ entries, whereas with an adjacency list, this is only requires going through $\Theta(V + E)$, since there are $V$ nodes and $2E$ total edges distributed across each vertex’s adjacency list (by the Handshaking Lemma.