Tree traversal

Also known as: Tree walk, Inorder, Preorder, Postorder, Level order

Tree traversal visits every node of a tree in a defined order. Depth-first styles: preorder (node, left, right), inorder (left, node, right), postorder (left, right, node). Level-order is BFS by depth.

Inorder on a BST yields sorted keys. Expression trees use inorder/postorder for print and evaluation. All visit $n$ nodes in $\Theta(n)$ time for an $n$-node tree.

Recursive DFS is the usual teaching form; iterative versions use an explicit stack or queue.

← Back to CS Glossary