CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
Helin Wang
Helin Wang

Reputation: 4202

Why BST left <= parent <= right is not ideal?

When allow duplicates, BST nodes typically has the following property: left <= parent < right, or: left < parent <= right.

What is wrong with left <= parent <= right?

Upvotes: 1

Views: 349

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59253

Your premise is incorrect. In a BST that allows duplicates, it's always left <= parent <= right. The code that picks the place to insert a new node will just pick one side or the other, but that is not a rule about how nodes must be linked and it is not an invariant that will be maintained.

That's because, for trees with duplicate values, the condition that the left or right branches contain only strictly larger elements is not compatible with balancing operations. Try this: link 20 copies of the same value into a tree. If you can only link equal values on the left or the right, then you have to make a singly-linked list. Your tree will be 20 levels deep and completely unbalanced.

The way to think about duplicate values in the tree is that there really aren't any duplicate values in the tree :-) A BST defines a total ordering, and valid rebalancing operations like rotations preserve this total ordering.

When you insert a duplicate into the tree, you'll put it either to the left or right of the existing match. If you put it on the left, then it will be smaller according to the ordering of the tree, and it will always be smaller after any rebalancing. If you put it on the right, then it will be larger, and will stay larger according to the tree's ordering.

If you think about it, it has to be this way because the balancing operations and in-order traversals don't even look at the values in the nodes. The way they're linked together determines the ordering, the ordering doesn't change as the tree is rebalanced, and the ordering is total -- every node is either before or after every other node in an inorder traversal.

Upvotes: 4

memo
memo

Reputation: 1938

If left <= parent <= right then in case of equality where would you go? Left or right? You need to be deterministic, not choose randomly. So let's say you decide to always use left, then there you go: left <= parent < right

Upvotes: 0

saketk21
saketk21

Reputation: 465

Because you need to maintain the O(log n) complexity for search. Consider you are searching for a Node, then you will have to check it in both the Left and Right subtree to check for its existence. However, the correct condition enforces the constraint that the Node will exist in only one of the subtrees.

Consider a scenario where the BST Node contains an Integer and a String, and the key for building the BST is the Integer.

If you need all the Strings for an integer a, you will need to check for both the subtrees, which will lead to a worse time-complexity of O(n) rather than the O(log n) if you implement it according to the correct condition.

Upvotes: 2

Related Questions