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

**Key takeaway:** An tree 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 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!

- 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

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

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

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

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

Find equilibrium index of an array

Write a program to find the equilibrium index of an array. An array's equilibrium index is an index such that sum of elements at lower indexes equal to the sum of elements at higher indexes. This is an excellent coding question to learn — how to optimize space complexity and solve the problem using a single scan.

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!