Tree Traversal

Systematic process of visiting each vertex of an ordered rooted tree exactly once.

Algorithms

Each defined recursively over subtrees $T_1, T_2, \ldots, T_n$ at root $r$ (left to right).

Preorder Traversal

Visit $r$, then traverse $T_1, T_2, \ldots, T_n$ each in preorder.

Mnemonic: root first, then subtrees left-to-right.

Inorder Traversal

Root after leftmost subtree. Traverse $T_1$ in inorder, visit $r$, then traverse $T_2, T_3, \ldots, T_n$ each in inorder.

Visits keys in sorted (ascending) order.

Postorder Traversal

Root last after 2 subtrees. Traverse $T_1, T_2, \ldots, T_n$ each in postorder, then visit $r$.