Tree Traversal | Sahithyan's Notes

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).

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

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

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.

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

Naming mnemonic: where the root appears.

Visual shortcut:

Draw a curve starting at root, tracing all edges counterclockwise:

Preorder - list a vertex the first time the curve passes it.
Inorder - list a leaf the first time passed; list each internal vertex the second time passed.
Postorder - list a vertex the last time passed (on the way back up to parent).