World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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.

#### Answered By : Hendrik Jan

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.