Tree Traversal Algorithms Cheat Sheet

Tree traversal algorithms

• Depth-First Traversal (DFT) = LIFO (stack + list)

Goes deep first.

• Breadth-First Traversal (BFT) = FIFO (queue + list)

Goes wide first.

Depth-First Traversal (DFT)

Inorder traversal

Left -> Root -> Right = Visit root in the middle.

go left
[Visit]
go right

Preorder traversal

Root -> Left -> Right = Visit root first.

[Visit]
go left
go right

Postorder traversal

Left -> Right -> Root = Visit root last.

go left
go right
[Visit]

Queue, Stack, List

Queue (FIFO) goes wide first

Stack (LIFO) goes deep first

Intuition

• Stack: “Where am I in the hierarchy?” (depth)
• Queue: “What are the next nodes to explore?” (breadth)
• List: “In what order did I see things?” (time)

Recursion vs. Iteration

• DFS: Recursion is fine when the tree is small and safe. Avoid for XML, HTML, JSON, etc. Use iterative DFS to avoid stack overflow.
• BFS: Never use recursion; it adds no value.