The Ordering Property

Solution

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.

Exercise

Is each binary tree below a binary search tree? If a tree is not, name a value that breaks the ordering property and the node it is on the wrong side of.

Tree A:

          ╭────╮
          │ 40 │
          ╰──┬─╯
   ┌─────────┴─────────┐
╭──┴─╮              ╭──┴─╮
│ 20 │              │ 60 │
╰──┬─╯              ╰──┬─╯
   └───┐           ┌───┘
    ╭──┴─╮      ╭──┴─╮
    │ 35 │      │ 45 │
    ╰────╯      ╰────╯

Tree B:

             ╭────╮
             │ 40 │
             ╰──┬─╯
   ┌────────────┴────────────┐
╭──┴─╮                    ╭──┴─╮
│ 20 │                    │ 60 │
╰──┬─╯                    ╰──┬─╯
   └───┐                 ┌───┘
    ╭──┴─╮            ╭──┴─╮
    │ 30 │            │ 50 │
    ╰────╯            ╰──┬─╯
                     ┌───┘
                  ╭──┴─╮
                  │ 35 │
                  ╰────╯

Solution

Tree A is a binary search tree. Tree B is not: 35 is in the right subtree of 40, but it is smaller than 40.

Solution

In-order visits the left subtree, then the node, then the right subtree. By the ordering property, every value in the left subtree is smaller than the node’s value and every value in the right subtree is larger. Each subtree is itself a binary search tree, so by the same argument the in-order traversal of each subtree visits its values in ascending order. The whole traversal visits the left subtree’s values in ascending order, then the node’s value, then the right subtree’s values in ascending order.