Does each level in a binary search tree need to be ordered?

Question

I'm reading about binary search trees, and most resources state that binary search trees need to abide by two rules (vs. regular trees):

• Each node has a maximum of up to two children.
• For each node, the values of its left descendent nodes are less than that of the current node, which in turn is less than the right descendent nodes (if any).

But does that mean we can have a tree where the levels are not in chronological order? For example, I found this image online and wasn't sure if it was a valid binary search tree since the third level from the top is not in order. So if I wanted to search for the number 4 I wouldn't know whether to search for it in the left or right branch.

Answer 1

This is not a binary search tree, as descendent nodes of a node u include all nodes that can be accessed going down a path starting at u.

Here 11 -> 12 -> 4 is a path down from 11, going first through the right child 12, so 4 is a right descendent node of 11. Since its value is smaller, this tree is not a binary search tree.

As a consequence of these rules, all layers are indeed sorted. In fact the whole in-order traversal is sorted.