Tree Traversals

Tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once.

Traversal Order

Tree traversals are different rules for visiting the same nodes

A tree traversal answers one question: in what order should we visit the nodes? The structure stays the same, but the order changes depending on whether you visit the node before its children, between its children, after its children, or level by level.

How to read the demo

Watch the visited order grow while the stack or queue changes beside it.

The active node shows where the traversal is working right now.

For the depth-first traversals, the side panel behaves like a call stack. For level order, it becomes a queue.

The message at each step explains why the traversal moved to that next node.

What to try in the demo

Run the same tree through all four orders and compare the visit sequence.

Step through Preorder, Inorder, and Postorder to compare the three depth-first patterns.

Switch to Level Order to see how the queue changes the exploration pattern completely.

Use Play, Step, and Reset to replay the same tree under different rules.

Compare preorder, inorder, postorder, and level order by stepping through the same tree.

Traversal Rule

Visit

Left

Right

Choose a traversal and step through the tree.

Call Stack (DFS)

Nodes waiting to return after exploring deeper.

Empty

Visit Order

Simulation Insight

DFS visits the node before exploring its children.

0 / 27

SlowFast

Traversal Types

The order changes, but the same tree is being visited every time

The best traversal depends on what your algorithm needs to do with each node and whether it needs a stack-style depth-first walk or a queue-style breadth-first walk.

Preorder

Visit node, then left subtree, then right subtree.

Creating or copying tree structure, prefix-style processing.

Inorder

Visit left subtree, then node, then right subtree.

Reading BST values in sorted order.

Postorder

Visit left subtree, then right subtree, then node.

Deleting or freeing a tree after processing children first.

Level order

Visit nodes breadth-first, one level at a time.

Shortest path by edge count in a tree or level-by-level processing.

Traversal	Visit Rule	Common Use
Preorder	Visit node, then left subtree, then right subtree.	Creating or copying tree structure, prefix-style processing.
Inorder	Visit left subtree, then node, then right subtree.	Reading BST values in sorted order.
Postorder	Visit left subtree, then right subtree, then node.	Deleting or freeing a tree after processing children first.
Level order	Visit nodes breadth-first, one level at a time.	Shortest path by edge count in a tree or level-by-level processing.

Key Takeaways

The short version

Traversal order changes the meaning of the same tree.
Preorder, inorder, and postorder are depth-first patterns built around a recursive call stack.
Level order uses a queue instead of a stack and explores one layer at a time.
Inorder on a binary search tree produces values in sorted order.