Faulty binary search tree

Hide text Hide pseudo-code

Below there is a faulty binary search tree in which duplicate keys are added to the left branch of the existing node, but while removing a node with two children, the removed node is replaced by a node in its right subtree. In correct solution, the replacement must be done from the same side than where the duplicates were added. Why?

Show a sequence of insertions and deletions that generates an inconsistent search tree. (Hint: the search routine only looks for duplicates in the left subtree)

Note: No model solution is available, because it would make the problem trivial.

Some additional problems.

  Created Fri Oct 30 13:52:50 EET 2009 - Powered by SVG-hut