0
$\begingroup$

A post claims 5 of the trees shown in the following figure are all binary search trees

enter image description here

I guess the author's making a mistake, since the 2 trees on the right ARE NOT binary search trees.

As an example, in the last tree pointed out by red rectangle, the key 1 is in 2's right subtree, which doesn't satisfy the binary-search-tree property.

Besides the figure above, the post also says

the BST is an ordered data structure that allows no duplicate values

which, I guess, is another mistake.

Correcting the bugs above, I'd like to make the following conclusion,

all the keys in a binary search tree should be greater than or equal to the root of the tree,

or more precisely, in a binary search tree, all the keys of a subtree should be greater than or equal to the root of the subtree,

is my understanding correct?

one of my references:

https://en.wikipedia.org/wiki/Binary_search_tree

$\endgroup$
2
  • $\begingroup$ No, you confuse with a min-heap. An author would not make such a gross mistake. A beginner could. $\endgroup$
    – user16034
    Sep 22, 2022 at 7:35
  • $\begingroup$ It is also true that a BST does not allow duplicate values, otherwise searches could be non-deterministic. $\endgroup$
    – user16034
    Sep 22, 2022 at 7:38

1 Answer 1

3
$\begingroup$

You are right that both trees on the right are not binary trees but you are wrong that all keys of a subtree are greater than the key at the root. It is true only for the right subtree. The keys of the left subtree are all lesser than the keys of the root. That is the very definition of a BST.

Concerning duplicated values, depending on whether you want to use your BST for representing sets or multisets, you can allow them or not, that will not change much the complexity of the underlying operations. In the textbook Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, duplicated values are allowed (see definition in Chapter 12).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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