Difficulty: Medium, Asked-in: Google

Key takeaway: An tree 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 values in the tree are unique.

Examples

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

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 recursive inorder traversal: using extra space
• Using recursive inorder traversal: without using extra space
• Using iterative inorder traversal: stack-based approach

Solution approach 1: A brute force approach by traversing the tree twice

There can be several possible pairs of nodes in a tree. 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. To do this, we need to traverse the tree twice:

• One traversal for accessing each node in the tree.
• Another traversal for finding the absolute difference with all other nodes and tracking the minimum difference so far.

We are traversing the tree once for each node in the tree. So time complexity = n*O(n) = O(n^2). Now the critical question is: can we solve this problem in O(n) time complexity or one traversal only? The given tree is a binary search tree. Can we solve this problem efficiently using the BST property? Let's think!

Solution approach 2: Using recursive inorder traversal and extra space

Solution idea

As we know that from the BST property: if we traverse BST using inorder traversal, it explore nodes in sorted order. Suppose we store node values in an extra memory. The critical question is: how can we find the min absolute difference in a sorted array. Let's think!

If we closely observe the sorted array, the difference between each element with its adjacent element is minimal compared to all other elements other than adjacent elements. In other words, rather than exploring all pairs, we need to find the difference between every pair of adjacent elements and track the minimum among them to get the value of the min absolute difference. We can do this in a single scan using O(n) time complexity. Note: here, we explore only (n-1) adjacent pairs rather than all possible pairs. Think!

BST node structure

class BSTNode
{
    int data
    BSTNode left
    BSTNode right
}

Solution pseudocode

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

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

Solution analysis

Time complexity = Time complexity of storing values in extra memory using 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 call stack for 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(h) 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). 

Solution approach 3: Using recursive inorder traversal without using extra space

Solution idea

Now critical questions are: can we solve this problem without using extra space? Can we track the absolute minimum difference during 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: we maintain an extra pointer to track the previous node in the in-order traversal. This will help in finding the difference between the current node and the previous node.

Now we traverse the tree using in-order traversal. For every node, 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 previous minimum difference, we update the minimum difference found so far.

Solution pseudocode

int findMinDiffBST(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)
}

Another implementation: Class-based

class MinDiffBST
{
    int minDiff = INT_MAX
    int prev = -1
    
    public int findMinDiffBST(BSTNode root) 
    {
        if (root == NULL) 
            return minDiff
        findMinDiffBST(root->left)
        if (prev >= 0)
            minDiff = min(minDiff, root->data - prev)
        prev = root->data
        findMinDiffBST(root->right)
        return minDiff
    }
    
}

Solution analysis

At each step of recursive in-order traversal, we are performing constant or O(1) operation with each node. So time complexity = Time complexity of in-order traversal = O(n)

Space complexity = Space complexity of recursive call stack for in-order traversal = O(h)

Solution approach 4: 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 previous minimum difference, we update the minimum difference found so far.

Solution pseudocode

int findMinDiffBST(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 using in-order traversal, 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? If yes, then what would be the time and space complexity?
• Can we solve this problem using threaded binary tree traversal or morris traversal?
• What would be the best and worst-case scenario of the space complexity in the above approaches?
• How can we design code for the brute force approach? Can we use the same traversal twice?
• 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 or negative in the BST?

Comparison of time and space complexities

• By traversing the tree twice: Time = O(n^2), Space = O(h)
• Using inorder and extra space: Time = O(n), Space = O(n)
• Using inorder traversal without extra space: Time = O(n), Space = O(h)
• Using iterative inorder traversal 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, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!