# Tree Traversal

Unlike linked lists, one-dimensional arrays and other linear data structures, which are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in depth-first or breadth-first order.

There are different ways to traverse a tree:

- pre-order traversal
- post-order traversal
- in-order traversal Depth-first traversal (dotted path) of a binary tree:

*Pre-order (node visited at position red ●)*:

F, B, A, D, C, E, G, I, H;*In-order (node visited at position green ●)*:

A, B, C, D, E, F, G, H, I;*Post-order (node visited at position blue ●)*:

A, C, E, D, B, H, I, G, F.

**Pre-order, NLR**

- Visit the current node (in the figure: position red).
- Recursively traverse the current node’s left subtree.
- Recursively traverse the current node’s right subtree.

**Post-order, LRN**

- Recursively traverse the current node’s left subtree.
- Recursively traverse the current node’s right subtree.
- Visit the current node (in the figure: position blue).

**In-order, LNR**

- Recursively traverse the current node’s left subtree.
- Visit the current node (in the figure: position green).
- Recursively traverse the current node’s right subtree