| 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. |