I was asked this question on a test and would like to make sure I answered correctly:
You are given a min heap. We want to increase all the nodes on the left most path (so the root, node 2, node 4, node 8......) by a value of c, so that the heap stays a min heap.
What is the limitation on c?
For instance, the min heap could be:
___2___
/ \
__8__ 7
/ \ / \
9 10 11 13
/ \ /
15 12 14
The left most path consists of the values 2, 8, 9 and 15
The expected answer is: c = 2
The increase of a node's value may not lead to a situation where that value becomes greater than one of its children's values. This is never an issue for the left child, since its value gets increased by the same amount, but it will become an issue for the right child, as that value does not change.
Among the nodes that are on the left most path (except the last one, which does not have a right child), you'll have to find the minimum difference between their right child's value, and their own value. That will be the maximum value that c can get.
In the example heap, these differences are (starting from the top):
7-2 = 5
10-8 = 2
12-9 = 3
The minimum of these differences is 2. So for the example the answer is 2.