Preorder vs inorder vs postorder vs level order

Tree traversal defines when each node is visited, not how the tree itself is stored. Preorder, inorder and postorder are common depth-first strategies for binary trees. Level order uses breadth-first traversal.

Same tree, four different answers

The example tree has root A, children B, C, and leaves D, E, F, G.

Strategy	Rule	Output
Preorder	Root, Left, Right	A B D E C F G
Inorder	Left, Root, Right	D B E A F C G
Postorder	Left, Right, Root	D E B F G C A
Level order (BFS)	Queue, shallower levels first	A B C D E F G

Visit order so far: –

Recursion stack: –

PreviousNext stepReset

Predict the next node before pressing Next step. Inorder depends on a defined left and right child.

Why the differences matter

Preorder records the parent before any descendant, useful for serialization and prefix notation. Inorder produces sorted keys only when the input is a correctly ordered binary search tree with an appropriate comparator. Postorder finishes child work before parent work, useful for bottom-up evaluation and deleting an owned subtree. Level order visits breadth-first, useful for finding nearest nodes by tree depth.

For a general multi-child tree, preorder and postorder have natural definitions if children have a specified order. Inorder depends on a designated left/right split and has no universal meaning for arbitrary numbers of children.

Runtime and memory

All four visit each of n nodes once: O(n) time. Depth-first recursive versions need O(h) call-stack space for height h. Level order holds a queue of up to O(w) nodes for tree width w. Collecting the full output takes O(n) regardless of traversal; streaming values avoids that output allocation.

Practice: Predict the four outputs for a tree with root A, a left child B and no right child, then switch modes in the explorer. Consider what happens if the tree degenerates into a chain.

References: GeeksforGeeks comparison, W3Schools tree traversal.