6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Juho
    Commented Jun 30, 2013 at 11:22
  • $\begingroup$ 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. $\endgroup$
    – Hendrik Jan
    Commented Jun 30, 2013 at 12:49
  • $\begingroup$ @HendrikJan All key values are unique. $\endgroup$
    – Robert S. Barnes
    Commented Jun 30, 2013 at 16:11

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think it's a (potentially helpful) rephrasing of the (generalized) claim. Note that any sequence has many compatible BSTs, though. $\endgroup$
    – Raphael
    Commented Jul 1, 2013 at 16:56
  • $\begingroup$ @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? $\endgroup$
    – Hendrik Jan
    Commented Jul 1, 2013 at 21:14
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jul 1, 2013 at 22:57
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.