Definition of BST and solution to 15.1

#1

Hello guys,

your definition of a binary search tree allows for duplicates at both sides, so you consider

    9
 /    \
9      9

a valid BST. I haven’t seen such definition before, most books and resources either disallow duplicates at all or allow duplicates only on one side (either left or right). Allowing duplicates on both sides makes it difficult to find all elements of some key or re-balance such a tree.

This also involves solution to 15.1 where you check:

Integer.compare(tree.data, lower) < 0 || Integer.compare(tree.data, upper) > 0

which in my opinion should be adjusted and include either >= or <=.

0 Likes
#2

Agree. Glad I ran into this post. I haven’t looked at 15.1 but do agree that text for definition of BST property can definitely be corrected - as it compares the current node with left sub tree node and right sub tree node for equality as well.

The code in 15.1 stands more in line with definition of BST on Wikipedia : “The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.” (https://en.wikipedia.org/wiki/Binary_search_tree)

0 Likes
#3

Thanks for the report, and you guys are right about the BST property. There shall be no duplicate elements in BST.

0 Likes
#4

Actually, I don’t see a problem, both with having duplicates, and with our program for testing if a binary tree is a BST.

Specifically, balancing is the same: you can use the heights at nodes, perform rotations, just like before (height has nothing to do with < or <=).

Similarly, if you are searching, if the key equals the root, you are done, so having keys equal to that at the root left and right makes no difference.

If you are looking for the first node with a given value, you can still do elimination, i.e., search left subtree when you get a hit.

0 Likes