**Difficulty:** Medium, **Asked-in:** Google

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

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.

```
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!

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

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.

```
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;
}
```

```
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
```

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).

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:

- In-order traversal explores BST nodes in sorted order.
- 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.

```
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;
}
};
```

```
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
```

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).

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.

```
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;
}
```

```
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
```

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!

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

- 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)

- 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!

☆ 16-Week Live DSA Course

☆ 10-Week Live DSA Course

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.

©2023 Code Algorithms Pvt. Ltd.

All rights reserved.