Visit every node of a tree in a fixed order: before its children (pre), between them (in) or after them (post).
Used for
7, 9, 5, 2, 11
5, 9, 2, 7, 11
5, 2, 9, 11, 7
Which order visits the root, 7, last?
Not quite. Post-order visits a node after both of its children, so the root comes last.
Step 1 of 5
A tree has no single first-to-last order, so we pick one. The three common orders differ only in when a node is visited compared with its children.
Step 2 of 5
Pre-order: the node first, then left, then right. Good for copying a tree.
Step 3 of 5
In-order: left, then the node, then right. On a binary search tree this gives the values in sorted order.
Step 4 of 5
Post-order: left, right, then the node. Children come before their parent, so it is the order for deleting a tree or adding up sizes.
Step 5 of 5
Your turn.
TreeAVL TreeRed–Black TreeDepth-First Search (tree)Breadth-First Search (tree)Binary Search Tree
function inorder(node, visit) { if (!node) return; inorder(node.left, visit); visit(node.val); inorder(node.right, visit);}