Tracing the Three Orders
A four-node tree is too small to show the pattern in each order clearly. From here on we use a larger tree, and we use the same one for all three traversals so you can compare the orders directly:
╭───╮
│ 5 │
╰─┬─╯
┌──────────┴──────────┐
╭─┴─╮ ╭─┴─╮
│ 8 │ │ 2 │
╰─┬─╯ ╰─┬─╯
┌────┴────┐ ┌────┴────┐
╭─┴─╮ ╭─┴─╮ ╭─┴─╮ ╭─┴─╮
│ 9 │ │ 1 │ │ 4 │ │ 7 │
╰─┬─╯ ╰───╯ ╰───╯ ╰─┬─╯
┌─┘ └─┐
╭─┴─╮ ╭─┴─╮
│ 6 │ │ 3 │
╰───╯ ╰───╯
Two nodes have a single child: 9 has only a left child, and 7 has only a right child. The values are not in any particular order.
There are four things to read in each trace below:
- Indentation shows how deep the recursion has gone; one step in is one call deeper.
preOrder(n)(orinOrder(n),postOrder(n)) is a call on noden, and the[...]after it says which childnis.visit n (k)prints noden, and the number(k)is its place in the print order.→ ...shows everything printed so far.
The trace leaves out the calls on missing children. Each of those calls hits the base case and returns without printing anything, the same way the calls on null in size return 0 at once.
Pre-order
Pre-order visits the node first, then the left subtree, then the right:
preOrder(5)
visit 5 (1) → 5
preOrder(8) [5's left]
visit 8 (2) → 5 8
preOrder(9) [8's left]
visit 9 (3) → 5 8 9
preOrder(6) [9's only child, on the left — a leaf]
visit 6 (4) → 5 8 9 6
preOrder(1) [8's right — a leaf]
visit 1 (5) → 5 8 9 6 1
preOrder(2) [5's right]
visit 2 (6) → 5 8 9 6 1 2
preOrder(4) [2's left — a leaf]
visit 4 (7) → 5 8 9 6 1 2 4
preOrder(7) [2's right]
visit 7 (8) → 5 8 9 6 1 2 4 7
preOrder(3) [7's only child, on the right — a leaf]
visit 3 (9) → 5 8 9 6 1 2 4 7 3
Here are the print positions on the tree:
╭───╮
(1) │ 5 │
╰─┬─╯
┌───────────────┴───────────────┐
╭─┴─╮ ╭─┴─╮
(2) │ 8 │ (6) │ 2 │
╰─┬─╯ ╰─┬─╯
┌──────┴───────┐ ┌──────┴───────┐
╭─┴─╮ ╭─┴─╮ ╭─┴─╮ ╭─┴─╮
(3) │ 9 │ (5) │ 1 │ (7) │ 4 │ (8) │ 7 │
╰─┬─╯ ╰───╯ ╰───╯ ╰─┬─╯
┌─┘ └─┐
╭─┴─╮ ╭─┴─╮
(4) │ 6 │ (9) │ 3 │
╰───╯ ╰───╯
The final order is:
5 8 9 6 1 2 4 7 3
Each node prints as soon as its call starts, so a node always prints before all of its descendants, and the root comes first.
In-order
In-order traverses the left subtree, then visits the node, then the right:
inOrder(5)
inOrder(8) [5's left]
inOrder(9) [8's left]
inOrder(6) [9's only child, on the left — a leaf]
visit 6 (1) → 6
visit 9 (2) → 6 9
visit 8 (3) → 6 9 8
inOrder(1) [8's right — a leaf]
visit 1 (4) → 6 9 8 1
visit 5 (5) → 6 9 8 1 5
inOrder(2) [5's right]
inOrder(4) [2's left — a leaf]
visit 4 (6) → 6 9 8 1 5 4
visit 2 (7) → 6 9 8 1 5 4 2
inOrder(7) [2's right]
visit 7 (8) → 6 9 8 1 5 4 2 7
inOrder(3) [7's only child, on the right — a leaf]
visit 3 (9) → 6 9 8 1 5 4 2 7 3
Here are the print positions on the tree:
╭───╮
(5) │ 5 │
╰─┬─╯
┌───────────────┴───────────────┐
╭─┴─╮ ╭─┴─╮
(3) │ 8 │ (7) │ 2 │
╰─┬─╯ ╰─┬─╯
┌──────┴───────┐ ┌──────┴───────┐
╭─┴─╮ ╭─┴─╮ ╭─┴─╮ ╭─┴─╮
(2) │ 9 │ (4) │ 1 │ (6) │ 4 │ (8) │ 7 │
╰─┬─╯ ╰───╯ ╰───╯ ╰─┬─╯
┌─┘ └─┐
╭─┴─╮ ╭─┴─╮
(1) │ 6 │ (9) │ 3 │
╰───╯ ╰───╯
The final order is:
6 9 8 1 5 4 2 7 3
Each node prints after its entire left subtree and before its right subtree. For the root, that puts 6 9 8 1 before 5 and 4 2 7 3 after. The reason is in the code: the print line comes after the call on the left subtree, and that call does not return until it has printed the whole subtree.
Post-order
Post-order traverses both subtrees first, and visits the node last:
postOrder(5)
postOrder(8) [5's left]
postOrder(9) [8's left]
postOrder(6) [9's only child, on the left — a leaf]
visit 6 (1) → 6
visit 9 (2) → 6 9
postOrder(1) [8's right — a leaf]
visit 1 (3) → 6 9 1
visit 8 (4) → 6 9 1 8
postOrder(2) [5's right]
postOrder(4) [2's left — a leaf]
visit 4 (5) → 6 9 1 8 4
postOrder(7) [2's right]
postOrder(3) [7's only child, on the right — a leaf]
visit 3 (6) → 6 9 1 8 4 3
visit 7 (7) → 6 9 1 8 4 3 7
visit 2 (8) → 6 9 1 8 4 3 7 2
visit 5 (9) → 6 9 1 8 4 3 7 2 5
Here are the print positions on the tree:
╭───╮
(9) │ 5 │
╰─┬─╯
┌───────────────┴───────────────┐
╭─┴─╮ ╭─┴─╮
(4) │ 8 │ (8) │ 2 │
╰─┬─╯ ╰─┬─╯
┌──────┴───────┐ ┌──────┴───────┐
╭─┴─╮ ╭─┴─╮ ╭─┴─╮ ╭─┴─╮
(2) │ 9 │ (3) │ 1 │ (5) │ 4 │ (7) │ 7 │
╰─┬─╯ ╰───╯ ╰───╯ ╰─┬─╯
┌─┘ └─┐
╭─┴─╮ ╭─┴─╮
(1) │ 6 │ (6) │ 3 │
╰───╯ ╰───╯
The final order is:
6 9 1 8 4 3 7 2 5
Every node prints after all of its descendants, so the root prints last. The print line comes after both recursive calls, and each call returns only after its whole subtree has printed.