In the tree where A has children B and C, B has children D and E, and C has only a right child F, what are the preorder, inorder, postorder and breadth-first sequences?

Preorder A B D E C F · inorder D B E A C F · postorder D E B F C A · breadth-first A B C D E F.

* C has only a right child, so F comes after C in inorder. *

* Same tree, four orders; the leaves D, E, F keep their relative order in the first three. *

Work each one out from its rule:

• Preorder (node, left, right): A, then B's subtree (B, D, E), then C's subtree (C, F).
• Inorder (left, node, right): B's subtree gives D, B, E; then A; then C's subtree. C has no left child, so C comes first and then F.
• Postorder (left, right, node): D, E, then B; F, then C; A last.
• Breadth-first (by level): A; B, C; D, E, F.

Quick checks that catch most mistakes: preorder always starts with the root, postorder always ends with it, and in inorder the root sits exactly between its left and right subtree's nodes.

Tip: a hand trick for the three depth-first orders is to trace a line around the tree counter-clockwise, starting left of the root. Preorder lists a node when the line passes its left side, inorder when it passes underneath, postorder when it passes its right side.

Go deeper:

• Tree traversal — depth-first search — a worked example of all orders on one binary tree, with the tracing picture.