Binary Search Tree Property

In the book 'Introduction to Algorithms 3/e', I have found the following definition of Binary Search Tree property:


Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree
of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

My confusion is that while implementing binary search trees we either consider that the keys of left-subtree of a node $x$ would be $\leq x.key$ or the keys of right-subtree of a node $x$ would be $\geq x.key$ but not both. That is we follow one of the two convention. But in the property they have included $=$ in both the cases. Where am I wrong?

I would appreciate any idea on this issue.

You're not wrong, but neither are they. The normal formulation is to have the left subtree values be strictly less than ($$), however using $\leq$ and $\geq$ still results in a working BST in the sense that the tree provides an ordering. (Try constructing a few, you'll see that the difference is that if you have repeated values, they can get spread over the right-most part of the left subtree and the left-most part of the right subtree instead of being in one or the other).

To see that it still works, consider the cases when searching the tree:

• $y = x$, you've already found it, so you can stop here;

• $y

• $y > x$, it must be in the right subtree.

So you can see that the operation is identical, the choice at each node remains unambiguous.

EDIT Just to highlight Svick's excellent point in the comments, if you're searching for all nodes with the same value, the "$\leq,\geq$" case introduces complications - it may require more than one pass to find all such nodes (a full traversal will get them all of course, if it's an inorder traversal you even get them in a row).

StackExchange Computer Science Q#3345, answer score: 7