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
Please write in the message below if you find anything incorrect, or you want to share more insight. Enjoy learning, Enjoy algorithms!