3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

You're not wrong, but neither are they. The normal formulation is to have the left subtree values be strictly less than ($<$) the current value and the right greater than or equal to ($\geq$) the current value, or vice versa ($\leq$ and $>$), 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:

  1. $y = x$, you've already found it, so you can stop here;
  2. $y < x$, it must be in the left subtree (if $y <x$ then $y \leq x$);
  3. $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).

$\endgroup$
  • 3
    $\begingroup$ But the choice can be ambiguous if you want to find all nodes with the same key. $\endgroup$ – svick Aug 28 '12 at 11:39
0
$\begingroup$

The equality is allowed when multiple nodes may have the same key.

Consider:

     c
  b     d
 a c   c e

In order to find all c elements, you have to descend both subtrees of the topmost c, but only the right subtree of b, and the left subtree of d.

$\endgroup$
  • $\begingroup$ So why they have such a property when we need to traverse both subtrees. Our target in tree searching would be to descend left or descend right. Is it to generalize tree ordering? $\endgroup$ – aghost Aug 28 '12 at 12:24
  • $\begingroup$ That depends on how the tree is balanced. If you rebalance the tree from my example so the rightmost c is on top, then you only need to go down the left path -- but then you have modified the constraint to disallow equality on the right subtree. $\endgroup$ – Simon Richter Aug 28 '12 at 12:53
  • $\begingroup$ I got these ideas but my focus is why they at all allow equality on both sides. Balancing is a concept which is not present in basic binary search trees. $\endgroup$ – aghost Aug 28 '12 at 16:11
  • 1
    $\begingroup$ Precisely because they do not want to think about balancing. Different insertion orders then lead to different tree layouts, so equal nodes can lie on either side. $\endgroup$ – Simon Richter Aug 29 '12 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.