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

• A brute force approach by traversing the tree twice
• Using extra memory and recursive inorder traversal
• In-place solution using recursive inorder traversal
• Using iterative inorder traversal: stack-based approach

A brute force approach by traversing the tree twice

If a tree has n nodes, total possible pair of nodes = nC2 = n(n - 1)/2. So one idea would be to explore all pairs, find absolute differences among them, and track the minimum difference so far. For this, we need to traverse the tree twice: One traversal for accessing each node and another traversal for finding the absolute difference with all other nodes. In other words, we need to traverse the tree once for each node.

Time complexity = n * O(n) = O(n^2). The critical question is: can we solve this problem using one traversal only? How can we think to solve this problem efficiently using the BST property? Let's think!

Using extra memory and recursive inorder traversal

Solution idea

As we know, inorder traversal of BST traverse nodes in sorted order. If we store node values in extra memory of size n, then the problem gets transformed to find the min absolute difference in a sorted array.

If we observe the sorted array, the difference between each element with its adjacent element is minimal compared to all other elements. So rather than exploring all pairs, we need to find the difference between n - 1 pair of adjacent elements and track the min absolute difference so far. We can do this in a single scan using O(n) time. Think!

Solution pseudocode

int absMinDiffBST(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
}

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

Solution analysis

Time complexity = Time complexity of in-order traversal + Time complexity of finding min absolute difference in the sorted array = O(n) + O(n) = O(n)

Space complexity = Space complexity of using an extra array of size n + Space complexity of recursive in-order traversal = O(n) + O(h) = O(n)

Note: the space complexity of recursive in-order traversal depends on the tree's height. In other words, we will only have as many frames on the call stack as the height of the tree. O(logn) in the best case (if the tree is entirely balanced) and O(n) in the worst-case (if we have a purely left-skewed or right-skewed tree). 

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! There are two critical insights from the above approach:

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

So one idea would be to find the difference between the current node and the previous node during the in-order traversal itself. For this, we can maintain an extra pointer to track the previous node.

• We traverse the tree using in-order traversal.
• For every node, we calculate the difference between the previous node.
• If the difference is smaller than the minimum difference so far, we update the minimum difference.

Solution pseudocode

int absMinDiffBST(BSTNode root)
{
    int minDiff = INT_MAX
    BSTNode prev = NULL 
    minDiffBST(root, prev, &minDiff)
    return minDiff
}

void minDiffBST(BSTNode root, BSTNode prev, int& minDiff)
{
    if (root == NULL) 
        return
    minDiffBST(root->left, prev, minDiff)
    if (prev != NULL)
        minDiff = min(minDiff, root->data - prev->data)
    prev = root
    minDiffBST(root->right, prev, 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 idea is similar to the above approach, but instead of using recursive inorder traversal, we are using iterative traversal with the help of a stack. The idea is: when we pop the current node from the stack, we compare the minimum difference found so far with the difference between the previous node and the current node. If this difference is smaller than the minimum difference so far, we update the minimum difference.

Solution pseudocode

int absMinDiffBST(BSTNode root)
{
    int minDiff = INT_MAX
    Stack<BSTNode> stack
    BSTNode curr = root
    prev = NULL
    while (stack.empty() == false || curr != Null) 
    {
        if (curr != NULL) 
        {
            stack.push(curr)
            curr = cur->left
        } 
        else 
        {
            curr = stack.pop()
            if (prev != NULL) 
                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!

Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

Critical ideas to think!

• How do we solve this problem if a tree is not BST? Can we think of using the above approaches?
• In the above approaches, why are we not taking the absolute value of (root->data - prev->data)? Is there a possibility that (root->data - prev->data) can be negative?
• Can we solve this problem using other traversals like pre-order, post-order, or level order?
• Can we solve this problem using threaded binary tree traversal or morris traversal?
• Why are we passing the minDiff parameter as a reference in the function call in the second approach? Can we think of some different ways to implement the code?
• 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!