1
$\begingroup$

Given a Binary Search Tree(BST) I would like to understand can absolute minimum difference between any two nodes of a BST is always between adjacent nodes. If Yes or No can we generalize it ? Assume there are atleast two nodes.

Here is my approach

Case 1 : Assume only positive real numbers

Assume the absolute difference (dMIN) between two adjacent nodes is not the Minimum This means there exists an absolute minimum difference which is smaller than dMIN by d. Say dMIN - d. In a BST, as we traverse left the value of the Node always decreases atleast by a smallest non zero value. Similiarly if we traverse to the right of a given node value of a node always increases atleast by smallest non-zero value This means the absolute min difference is always greater dMIN atleast by smallest non-zero value Which contradicts there exists a smaller absolute dMIN - d. Thus the absolute minimum difference is always absolute difference of two adjacent nodes

Case 2 - Assume the nodes of the BST comprises entire set of real numbers. There exists atleast one negative real number.

Assume there exists a min absolute difference(dMIN) two adjacent nodes. Since the value of the nodes comprises entire set of real numbers As we traverse to the left side of node the value of the node decreases atleast by the largest negative number. This can be continued until we reach leaf nodes from the root node. Thus the absolute min difference increases as we traverse from the root node to the left most leaf node. Thus absolute min difference of a pair of nodes is always between root node and leaf node.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Jul 11, 2021 at 0:10
  • $\begingroup$ I have updated the question. Coming to your point "If you just need someone to check your work, you might seek out a friend, classmate, or teacher. ". Well I don't have a peer to do that that is why I wanted to check in stackexchange. $\endgroup$
    – Kranthi Kiran
    Commented Jul 11, 2021 at 5:29
  • $\begingroup$ Unfortunately "is my proof correct?" is normally not the kind of question we are looking for in CS Stack Exchange, as it is so unlikely that anyone else will have exactly the same question in the future. If you don't have anyone else who can help, I sympathize, but that doesn't change the bottom line about whether such questions are what we're hoping for here. $\endgroup$
    – D.W. ♦
    Commented Jul 11, 2021 at 5:32
  • $\begingroup$ I updated the question even further. $\endgroup$
    – Kranthi Kiran
    Commented Jul 11, 2021 at 5:44

1 Answer 1

Reset to default
1
$\begingroup$

Your proof for case 1 seems like good intuition (it is not a formal proof). However, instead of the proof in case 2, you can directly reduce case 2 to case 1:

Lets say that the minimal value in the tree is $v_{min}\in\mathbb{R}$. Then, we can artificially "add" $v_{min}$ to the value of every node in the BST. Now, the BST will contain only non-negative numbers. This BST will follow case 1.

I claim, that for any two nodes with values $v'_1$, $v'_2$ in this updated BST, their absolute difference is the same as their absolute difference from the original BST, that had values $v_1,v_2$ in them:

$$|v'_2-v'_1|=|v_2+v_{min}-(v_1+v_{min})|=|v_2-v_1+v_{min}-v_{min}|=|v_2-v_1|$$

And hence the proof for case 1 works here as well.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I have updated the question as per community rules. Just bringing to your notice as your answers needs an update under the changed context. $\endgroup$
    – Kranthi Kiran
    Commented Jul 11, 2021 at 5:54
  • $\begingroup$ @KranthiKiran I think you have misunderstood them. Questions that ask whether your proof is correct or not, are not as useful. But asking the question, and then writing what your opinion on the matter is - is more than welcomed in this site (we encourage research efforts before posting a question). So I believe you can still include that part of the question. Just phrase it differently, so it won't sound like you want someone to validate your proof, but rather you are asking a more general question. $\endgroup$
    – nir shahar
    Commented Jul 11, 2021 at 8:20
  • $\begingroup$ OK. I rephrased the question also brought my understanding back to the table. $\endgroup$
    – Kranthi Kiran
    Commented Jul 14, 2021 at 11:42

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.