Tree traversal methods

Traversal visits every node in a fixed order. For binary trees, depth-first orders are named by when the root of each subtree is processed relative to its children.

On this page
  • DFS orders: preorder, inorder, postorder (table)
  • BFS: level order (queue)
  • Mini example visit order

1) Depth-first traversals (binary tree)

Assume for each node you process left subtree before right. “Root” below means the current node’s value (or visit action).

Three classic DFS orders
Order Sequence at each node Typical use
Preorder Root → left → right Copying a tree, prefix-style export, building from traversal with markers.
Inorder Left → root → right BST: visits keys in sorted order (for numeric/string keys with the usual ordering).
Postorder Left → right → root Deleting or freeing subtrees bottom-up, postfix evaluation of expression trees.

2) Breadth-first (level order)

Visit nodes level by level, left to right within a level. Usually implemented with a queue (FIFO)—see Level order traversal (binary tree) and BFS with a queue.

3) DFS vs BFS (summary)

Traversal families
Family Mechanism Extra space (typical)
DFS Recursion (implicit stack) or explicit stack O(h) for height h of recursion/stack
BFS / level order Queue of frontier nodes O(w) for max width, up to O(n)

Tiny binary tree (visit order sketch)

       2
     /   \
    1     3

Preorder:  2, 1, 3
Inorder:   1, 2, 3
Postorder: 1, 3, 2
Level order: 2, 1, 3

Key takeaway

Memorize where the root prints in preorder / inorder / postorder; on a BST, inorder is your sorted walk. Use level order when you need layer-by-layer processing or shortest steps in an unweighted tree-shaped graph.

Next up: Tree representation · Binary tree operations · Binary tree using array