The Ordering Property

In the tree chapter, I noted that if we draw all the choices binary search could make over a sorted array, we get a binary tree. Here is the example I used for the sorted array [10, 20, 30, 40, 50, 60, 70]:

         40
    ┌─────┴─────┐
   20           60
 ┌──┴──┐     ┌──┴──┐
10     30   50     70

The root, 40, is the first value binary search checks. Everything in its left subtree is smaller than 40: 10, 20, 30. Everything in its right subtree is larger: 50, 60, 70. The same is true at 20 and at 60. Binary search depends on that ordering. At any node, one comparison tells us which subtree could still contain the target and which one we can ignore.

In that chapter, the array was the real structure, and the tree was just a picture of the search. What if we store the values in the tree directly? Then we do not keep an array sorted and run binary search over positions. We keep a binary tree whose left and right subtrees already mean “smaller” and “larger.” That structure is a binary search tree: a binary tree where, at every node,

• every value in the left subtree is smaller than the node’s value, and
• every value in the right subtree is larger than the node’s value.

The word every matters. It is not enough for a node to be larger than its left child and smaller than its right child. Look at this tree:

       ╭────╮
       │ 50 │
       ╰──┬─╯
   ┌──────┴──────┐
╭──┴─╮        ╭──┴─╮
│ 30 │        │ 70 │
╰──┬─╯        ╰────╯
   └─┐
  ╭──┴─╮
  │ 60 │
  ╰────╯

If you only compare each node with its children, every check passes. 30 is less than 50. 70 is greater than 50. 60 is greater than 30. But 60 sits in the left subtree of 50, and every value in that subtree must be smaller than 50. It is not, so this is not a binary search tree. This is a common mistake. A parent-child check sees only one edge at a time.

Here is another tree:

       ╭────╮
       │ 50 │
       ╰──┬─╯
   ┌──────┴──────┐
╭──┴─╮        ╭──┴─╮
│ 25 │        │ 75 │
╰────╯        ╰──┬─╯
               ┌─┘
            ╭──┴─╮
            │ 55 │
            ╰────╯

This one is valid. 55 is smaller than 75, so it belongs in 75’s left subtree. It is also larger than 50, so it is allowed to be somewhere in 50’s right subtree. A value has to be on the correct side of every ancestor above it, not just its parent.

In this chapter we keep the duplicate rule simple: no duplicates. Every value appears at most once. Real implementations may choose a convention for equal values, such as putting duplicates on one side or storing a count in the node, but we will not need that here.