Question

You are given a Binary Search Tree containing integers. How would you in linear time find the least difference between the values of any two node in the BST.

Answer 1

Here is the algorithm

In order traversal of a BST traverses it in sorted order. So, for every node, we will find its difference from the previous node in the in-order traversal of the tree. If this difference is smaller than the previous minimum difference, we will update the previous minimum difference. Following are the steps to follow:

1. First create a variable ‘prev’ to store the pointer to the previous node in in-order traversal.
2. Then create a variable ‘ans’ to store the minimum difference.
3. Now, for every node in the in-order traversal, we need to compare its absolute difference with the previous node and then update the minimum absolute difference found so far.

Here is the pseudocode:

function inorder(Node curr) {

    if (curr is null)

        return;

    inorder(curr.left);

      

    if (prev is not null)

        ans = Math.min(curr.data - prev.data, ans);

    prev = curr;

    inorder(curr.right);

}

function minDiff(BST root) {

    prev = NULL;

    ans = INT_MAX;

inorder(root, prev, ans);

    return ans;

}