Question

Suppose a binary search tree has multiple nodes containing the same key value, k. Let node p be the lowest common ancestor of such nodes. Then, the key of p must be also k. If this is true, provide an argument. Otherwise, provide a counterexample.

Answer 1

Lets first define the BST rule as all keys in left subtree of a key must be smaller and all keys in right subtree must be greater or equal (as we are dealing with duplicate keys).We can also define the rule other way as all keys in left subtree of a key must be smaller or equal and all keys in right subtree must be greater. From now lets stick with the first option as all keys in left subtree of a key must be smaller and all keys in right subtree must be greater or equal.

Now Lowest common ancestor of two nodes say x and y is basically the first node that is common in both the sequences(that is x->root and y->root) of nodes in the path from that particular node to root.

Now suppose we assume that two nodes(k_1 and k_2) with same key value k has a lowest common ancestor p which is different from k.so as per the definition of lowest common ancestor p must be first common node in both sequence k_1 -> root and k_2 -> root, and k_1 and k_2 must be in two different side of p(if they are on the same side than p will not be the lowest common ancestor in the first place) but this is contradiction as same key value node must be go to same left or right subtree of the parent node.

So,lowest common ancestor of two nodes containing the same key value, k has to be same value as k.