In-order Is Sorted

Recall in-order traversal from the tree chapter: visit the left subtree, then the node, then the right subtree. When we ran it on binary search’s decision tree, it listed the values in sorted order.

In-order traversal does the same on a binary search tree. Here is our tree:

                ╭────╮
                │ 50 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 70 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 40 │      │ 60 │    │ 80 │
╰────╯    ╰────╯      ╰────╯    ╰────╯

In-order visits its values in this order:

20  30  40  50  60  70  80

The reason is the ordering property. At every node, in-order visits the whole left subtree first, then the node, then the right subtree. Every value in the left subtree is smaller than the node, and every value in the right subtree is larger. Each subtree is itself a binary search tree, so by the same argument its in-order traversal is sorted. Putting the three parts together gives:

┌───────────────────────┬────────────┬────────────────────────┐
│ sorted left values... │ node value │ sorted right values... │
└───────────────────────┴────────────┴────────────────────────┘