# Binary Search Tree: Replace $k$ min elements with their average

Given a valid binary search tree whose keys are unique real numbers, and a set of $k$ pointers to the $k$ minimum elements in the tree, will the BST property be maintained if I replace all $k$ elements with the average of the $k$ elements?

The BST property as given in Corman:

Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

I've tried this with a few test cases for $k=3$ and a few different trees, and it seems to hold, but I'm not sure if it actually does and how I could prove it.

• It's always a good idea to consider extreme values and possible corner cases. So what if $k=0$, $k=1$, or $k=n$? Seems to hold in all these cases too, hey? – Juho Jun 30 '13 at 11:22
• Are all values initially different? If so I gues it is true. Otherwise it isn't. Have a BST with all values equal, except one which is less than the rest (i.e., left-most in the tree). Assume the root has both children present. Now change all values to the mean except for the root. The root now has both children smaller than itself. – Hendrik Jan Jun 30 '13 at 12:49
• @HendrikJan All key values are unique. – Robert S. Barnes Jun 30 '13 at 16:11

The following is either a proof, or an argument that runs in circles.

Given a binary search tree the ordered sequence of keys can be retrieved using the symmetric inorder traversal. Conversely any ordered sequence of keys can be stored in a binary tree with the BST property only if the keys are mapped precisely in inorder. (Proof: the root has a unique value as all keys the the left must be smaller, to the right must be larger. Use recusion for the subtrees).

Now take a BST tree and retrieve its keys in order. Take any consecutive segment of the keys and replace these keys by any value between the first and last of the segment. The result is again an ordered sequence of keys and remapping to the original tree will give again a BST.

Taking the minimum $k$ values and replacing with the mean is a special case.

• I think it's a (potentially helpful) rephrasing of the (generalized) claim. Note that any sequence has many compatible BSTs, though. – Raphael Jul 1 '13 at 16:56
• @Raphael True. In the question the tree is given, so is fixed. You say "rephrasing", whereas I intend it as a proof. Replacing a segment by another increasing sequence can be mapped onto the same tree using inorder and forms a BST. Where should I add more detail to convince you? – Hendrik Jan Jul 1 '13 at 21:14
• Okay, I guess it is a proof idea at least. For a rigorous proof, well, one had to show that it works, that is that the BST property (still) holds. But since you can do that directly, no need to go over the sorted list. – Raphael Jul 1 '13 at 22:57

Let $M = \{T_{(1)}, \dots, T_{(k)}\}$ the set of the $k$ smallest elements in a BST $T$. Replace all elements in $M$ with $\tfrac{1}{n} \cdot \sum_{i=1}^k T_{(i)}$.

Let $x$ some node in $T$ and $y$ some other node in the left (right) subtree of $x$. Perform a complete case distinction:

1. $x,y \in M$
2. $x \in M$, $y \notin M$
3. $x \notin M$, $y \in M$
4. $x, y \notin M$

Show for all cases that they either can not occur, or that the BST property still holds.