Minimum Absolute Difference in BST

68.9k
0

Given the root of a Binary Search Tree (BST), your objective is to find the Minimum Absolute Difference in BST between the values of any two different nodes present in the tree. You must return this smallest possible difference as an integer.

Example 1

Input: [4, 2, 6, 1, 3, null, null]

Output: 1

Explanation: The sorted node values are 1, 2, 3, 4, 6. The minimum absolute difference is 1, which occurs between 2 and 1, 3 and 2, or 4 and 3.

Example 2

Input: [1, 0, 48, null, null, 12, 49]

Output: 1

Explanation: The sorted node values are 0, 1, 12, 48, 49. The smallest difference found is between 1 and 0, or between 49 and 48, both resulting in 1.

Brute Force Approach

Consider a scenario where you are tasked with finding the smallest gap in test scores among a classroom of students. If you randomly pick pairs of students to compare, it will take a massive amount of time. However, if you force all students to line up sequentially from the lowest score to the highest score, finding the smallest gap becomes incredibly simple. You only need to compare the scores of students standing directly next to each other.

A Binary Search Tree operates on a strict rule: the left side is always smaller than the root, and the right side is always larger. By reading the tree in a specific "Left-Root-Right" order, we naturally extract the values in a perfectly sorted sequence. We can write these sorted numbers down in an array, and then loop through the array to find the smallest gap between adjacent numbers.

If you want to understand this in detail, check our guide on Tree Traversals.

Algorithm

  • Create a dynamic array to store the values of the tree nodes.

  • Create a recursive function to perform an inorder traversal.

  • Within the recursive function, visit the left child, append the current node's value to the array, and then visit the right child to get the current difference.

  • After fully traversing the tree, initialize a variable to store the minimum difference, setting it to a very large number.

  • Loop through the array from the first index to the end.

  • In each iteration, calculate the difference between the current element and the previous element.

  • Update the minimum difference variable if the calculated difference is smaller.

  • Return the final minimum difference.

Dry Run

Minimum Absolute Difference in BST Brute Dry Run

Minimum Absolute Difference in BST Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
// Definition for a binary tree node
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
private:
// Recursive function to extract tree values in ascending sorted order
void inorder(TreeNode* root, vector<int>& values) {
// Base condition stops the traversal when an empty branch is encountered
if (root == nullptr) {
return;
}
// Traverse the left branch to reach the smallest possible values first
inorder(root->left, values);
// Store the current node's value to build our sorted array
values.push_back(root->val);
// Traverse the right branch to process larger values
inorder(root->right, values);
}
public:
// Main function to compute the minimum difference using the collected array
int getMinimumDifference(TreeNode* root) {
vector<int> values;
// Populate the array with sorted elements from the tree
inorder(root, values);
int minDiff = INT_MAX;
// Iterate through adjacent pairs in the sorted array to find the smallest gap
for (int i = 1; i < values.size(); i++) {
// Update the minimum difference if the current gap is strictly smaller
minDiff = min(minDiff, values[i] - values[i - 1]);
}
return minDiff;
}
};
// Driver code starts here
int main() {
// Constructing the binary search tree manually for testing purposes
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(6);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
Solution obj;
// Executing the logic and storing the result
int result = obj.getMinimumDifference(root);
// Displaying the final answer to the user
cout << "Minimum Absolute Difference: " << result << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the total number of nodes in the tree. We visit every single node to construct our array, and then we loop through the array once.

Space Complexity: O(N), because we are creating an external array that stores every single node value from the tree.

Optimal Approach

Why the previous approach is inefficient: The first approach wastes a significant amount of system memory by storing every single value inside an array. If a tree has millions of nodes, we allocate memory for millions of integers, even though we only ever need two adjacent numbers at any given time.

What improvement this approach brings: We completely remove the need for an external array. We calculate the difference on the fly during the tree traversal by simply keeping track of the previous node we just looked at.

Consider a factory assembly line where boxes sorted by weight roll past a single inspector. The inspector needs to find the smallest weight difference between two consecutive boxes. Instead of pulling every single box off the line and writing down its weight in a massive ledger, the inspector only needs to hold the previous box's weight in their head, compare it to the current box, update their smallest difference record, and then forget the old weight to memorize the new one.

We can apply this directly to our tree. While performing our standard ascending traversal, we maintain a prev variable. Whenever we land on a node, we subtract prev from the current node's value. We update our lowest recorded difference, and then we assign the current node's value to prev before moving on.

Algorithm

  • Declare global or class-level variables: minDiff initialized to a large value, and a prev node pointer initialized to null (or a variable tracking the previous integer).

  • Create an inorder traversal function to traverse the tree.

  • Traverse to the left child first for smaller value first.

  • Process the current node: If prev is not null, calculate the difference between the current node's value and the prev value. Update minDiff if this new difference is smaller.

  • Update prev to point to the current node.

  • Traverse to the right child.

  • Call the function from your main method and return minDiff.

Dry Run

Minimum Absolute Difference in BST Optimal Dry Run

Minimum Absolute Difference in BST Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
// Definition for a binary tree node
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
private:
// State variables held at the class level to persist across recursive calls
int minDiff = INT_MAX;
TreeNode* prev = nullptr;
// Optimal inorder traversal calculating differences without extra storage
void inorder(TreeNode* root) {
// Base case to stop execution when an empty node is reached
if (root == nullptr) {
return;
}
// Process left branch first to maintain ascending order
inorder(root->left);
// If a previous node exists, evaluate the gap between it and the current node
if (prev != nullptr) {
minDiff = min(minDiff, root->val - prev->val);
}
// Update the previous pointer to the current node before moving forward
prev = root;
// Process right branch for larger values
inorder(root->right);
}
public:
// Main function acting as the trigger for the traversal
int getMinimumDifference(TreeNode* root) {
inorder(root);
return minDiff;
}
};
// Driver code starts here
int main() {
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(6);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
Solution obj;
int result = obj.getMinimumDifference(root);
cout << "Minimum Absolute Difference: " << result << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), because we still traverse every single node in the tree exactly once.

Space Complexity: O(H), where H is the height of the tree. This space complexity comes strictly from the recursive call stack. We are no longer using any external arrays to map the values.

Interview follow-up Questions

In standard binary search trees, duplicate values are typically not allowed. However, if the tree structure you are working with does allow duplicates, then yes, the minimum difference can be zero.

Binary Search TreeMathsRecursionStack

Read Similar Blogs

MathsIntroduction to DSA

Mastering Number Basics in Programming

Introduction Numbers are one of the first things that appear in DSA, and they are much friendlier than they look. A number can be checked, divided, broken into digits, counted, and compared. These...

73.6k
MathsGreedyIntroduction to DSA

Find Remainder

Given two non-negative integers a and b , find the remainder when a is divided by b . Assume b is not 0 . Approach The small observation is very direct: the remainder is exactly what the modulo ope...

95.9k
Introduction to DSABit ManipulationMaths

Check Even or Odd

Given an integer N , determine whether it is even or odd. Return "Even" if the number is divisible by 2 , otherwise return "Odd" . Approach The first observation is the whole key: even and odd numb...

68.5k
Comments0