Can the minimum value of a binary search tree not be the leftmost entry?

Question

If I construct a binary search tree as I have below, is it right? Or is such a tree not a valid binary search tree?

    7
   / \
  5   8
     / \
    4  10

Because I have followed the rule of smaller element on the left and larger element on the right. So I imagine this is a binary search tree?

Answer 1

Try to walk the tree manually; pretending that you're a function looking for the 4.

• You start at the root of the tree: the 7.
• 4 is less than 7, so you go left to 5.
• 4 is less than 5 so you go left again.
• There's nothing there, so you'd come to the conclusion that 4 is not in the tree.

Of course that's incorrect though, so no, this is not a valid setup for a BST. It isn't simply that each value needs to only be in the correct position relative to its direct parent. Each value also needs to be in a correct position relative to the other nodes in the tree.

The exact position depends on the insertion order of each value, but with this configuration of values, the 4 should be to the left of the 5.