Find Minimum Absolute Difference in Binary Search Tree (BST)

Difficulty: Medium, Asked-in: Google

Key takeaway: An excellent problem to learn problem-solving using in-order traversal.

Let’s understand the problem!

Given the root of a binary search tree (BST), write a program to return the absolute minimum difference between the values of any two nodes in the tree.

• The node values in the tree can be positive, negative, or zero.
• Assume all node values in the tree are unique.

Examples

Input: 
          10 
        /   \ 
      -2     13 
      / \   / \ 
    -4   7 11  18

Output: 2
Explanation: Among all pair of nodes, the absolute difference 
between pair of nodes (-2, -4) and (13, 11) is 2, which is 
minimum. So we return 2 as an output.

Input:
          10 
        /   \ 
       5     13 
               \ 
               18
Output: 3
Explanation: Difference between pair of nodes (10, 13) is minimum. 

Important note: before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Discussed solution approaches

• Using extra memory and recursive inorder traversal
• In-place solution using recursive inorder traversal
• Using iterative inorder traversal: stack-based approach

Using extra memory and recursive inorder traversal

Solution idea

We can use an in-order traversal to traverse a binary search tree (BST) in sorted order. Suppose we store the values of the nodes in an extra array of size n. In that case, we can transform the problem into finding the absolute minimum difference between any two elements in a sorted array.

If we examine the sorted array, we can see that the difference between each element and its adjacent element will be smaller than the difference between any other pair of elements. Therefore, instead of comparing all pairs of elements, we only need to find the difference between the n-1 pairs of adjacent elements and keep track of the absolute minimum difference we have seen. We can do this in a single pass through the array in O(n) time.

Solution code C++

void inorder(BSTNode* root, vector<int>& sorted) 
{
    if (root == NULL)
        return;
    inorder(root->left, sorted);
    sorted.push_back(root->data);
    inorder(root->right, sorted);
}

int minAbsoluteDifferenceBST(BSTNode* root) 
{
    if (root == NULL)
        return INT_MAX;
 
    vector<int> sorted;
    inorder(root, sorted);
    int n = sorted.size();
    int minDiff = INT_MAX;
    
    for (int i = 1; i < n; i = i + 1) 
    {
        int diff = sorted[i] - sorted[i - 1];
        if (diff < minDiff)
            minDiff = diff;
    }
    
    return minDiff;
}

Solution code Python

def inorder(root, sorted):
    if root is None:
        return
    inorder(root.left, sorted)
    sorted.append(root.data)
    inorder(root.right, sorted)

def minAbsoluteDifferenceBST(root):
    if root is None:
        return sys.maxsize
    
    sorted = []
    inorder(root, sorted)
    n = len(sorted)
    minDiff = sys.maxsize
    
    for i in range(1, n):
        diff = sorted[i] - sorted[i - 1]
        if diff < minDiff:
            minDiff = diff
    
    return minDiff

Solution analysis

The time complexity of this algorithm is the sum of the time complexity of the in-order traversal and the time complexity of finding the minimum absolute difference in the sorted array, which is O(n) + O(n) = O(n).

The space complexity of this algorithm is the sum of the space complexity of using an extra array of size n and the space complexity of the recursive in-order traversal, which is O(n) + O(h).

The space complexity of the recursive in-order traversal depends on the height of the tree. In the best case (when the tree is completely balanced), the height is O(logn), and in the worst case (when the tree is purely left-skewed or right-skewed), the height is O(n). Therefore, the overall space complexity is O(n).

In-place solution using recursive inorder traversal

Solution idea

The critical questions are: Can we solve this problem in place or without using extra space? Can we track the absolute minimum difference using inorder traversal? Let's think!

To solve this problem without using extra space or doing an in-order traversal, we can find the minimum absolute difference between adjacent values during the in-order traversal. Two key insights will be useful for this approach:

1. In-order traversal explores BST nodes in sorted order.
2. In a sorted order, we need to compare the difference between adjacent values in order to find the minimum absolute difference.

To implement this idea, we can maintain an extra variable to track the value of the previous node during the in-order traversal. As we traverse the tree, we can calculate the difference between the current node and the previous node. If this difference is smaller than the minimum difference we have seen so far, we can update the minimum difference.

Solution code C++

class Solution {
private:
    int minDiff = INT_MAX;
    int prev = INT_MIN;

public:
    int findMinimumDifference(TreeNode* root) {
        if (root == NULL) 
            return minDiff;

        findMinimumDifference(root->left);
        if (prev != INT_MIN)
            minDiff = min(minDiff, root->data - prev);

        prev = root->data;
        findMinimumDifference(root->right);
        return minDiff;
    }
};

Solution code Python

class Solution:
    def __init__(self):
        self.minDiff = sys.maxsize
        self.prev = -sys.maxsize

    def findMinimumDifference(self, root):
        if root is None:
            return self.minDiff

        self.findMinimumDifference(root.left)
        if self.prev != -sys.maxsize:
            self.minDiff = min(self.minDiff, root.data - self.prev)

        self.prev = root.data
        self.findMinimumDifference(root.right)
        return self.minDiff

Solution analysis

We are performing O(1) operation with each node at each step of in-order traversal. So time complexity = Time complexity of in-order traversal = O(n). Space complexity = Space complexity of recursive in-order traversal = O(h).

Using iterative inorder traversal

Solution idea

This approach is similar to the previous one, but it uses an iterative in-order traversal with the help of a stack instead of a recursive in-order traversal. The basic idea is to pop the current node from the stack and compare the minimum difference found so far with the difference between the previous node and the current node. We update the minimum difference if this difference is smaller than the minimum difference.

Solution code C++

int absMinDiffBST(BSTNode* root)
{
    int minDiff = INT_MAX;
    stack<BSTNode*> stack;
    BSTNode* curr = root;
    BSTNode* prev = NULL;
    while (stack.empty() == false || curr != NULL)
    {
        if (curr != NULL)
        {
            stack.push(curr);
            curr = curr->left;
        }
        else
        {
            curr = stack.top();
            stack.pop();
            if (prev != NULL)
                minDiff = min(minDiff, curr->data - prev->data);
            prev = curr;
            curr = curr->right;
        }
    }
    return minDiff;
}

Solution code Python

def absMinDiffBST(root):
    minDiff = sys.maxsize
    stack = []
    curr = root
    prev = None
    while len(stack) == 0 or curr is not None:
        if curr is not None:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            if prev is not None:
                minDiff = min(minDiff, curr.data - prev.data)
            prev = curr
            curr = curr.right
    return minDiff

Solution analysis

We are traversing each node only once and performing O(1) operation with each node. So time complexity = Time complexity of in-order traversal = O(n). Space complexity = Space complexity of using stack for in-order traversal = O(h). Think!

Critical ideas to think!

1. Can we use the above approaches to solve the problem if the tree is not a BST?
2. Can we solve the problem using other traversals, such as pre-order, post-order, or level-order traversal?
3. Can we solve the problem using threaded binary tree traversal or Morris traversal?
4. Does the above solution work perfectly when values are repeated in the BST?

Comparison of time and space complexities

• By traversing the tree twice: Time = O(n^2), Space = O(h)
• Inorder and extra space: Time = O(n), Space = O(n)
• Inorder without extra space: Time = O(n), Space = O(h)
• Iterative inorder using stack: Time = O(n), Space = O(h)

Suggested coding problems to practice

• Recursive and iterative in-order traversal
• K-diff Pairs in an Array
• Find the minimum absolute difference in two different BST’s
• Kth smallest element in a BST

Please write in the message below if you find anything incorrect, or you want to share more insight. Enjoy learning, Enjoy algorithms!