Minimum Absolute Difference in BST solution and explanation
Google
9 more videos on this problem
Minimum Absolute Difference in BST - Leetcode 530 - Trees (Python)Greg Hogg · 6:31 · 11K views
Minimum Absolute Difference in BST | Leetcode-530 | GOOGLE | Explanation ➕ Live CodingcodestorywithMIK · 18:02 · 10K views
Minimum Absolute Difference in BST | Leetcode - 530Algorithms Made Easy · 14:07 · 5K views
Minimum Absolute Difference in BST | LEETCODE - 530 | Easy solutionhi-malik · 8:06 · 5K views
530. Minimum Absolute Difference in BST | English | EasySimple Code - 단순코드 · 5:40 · 2K views
530. Minimum Absolute Difference in BST | Inorder Traversal | BFS | LeetCode Daily ChallengeDeep Tech · 11:30 · 2K views
Leetcode #530: Minimum Absolute Difference in BST C++ SolutionZakaria Ridouh · 6:59 · 2K views
LeetCode 530 Minimum Absolute Difference in BSTJeevan Kumar - Cracckify · 5:30 · 2K views
Minimum Absolute Difference in BST - Leetcode 530 - Python (Recursive And Iterative Approach)TechError · 13:34 · 818 views
Minimum Absolute Difference in BST - Leetcode 530 - PythonAlgorithms Casts · 8:20 · 528 views
The problem
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3] Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49] Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 104]. 0 <= Node.val <= 105
Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
Approach overview
Problem Overview: You are given the root of a Binary Search Tree and must return the minimum absolute difference between values of any two different nodes. Because the tree follows BST ordering rules, an efficient solution relies on processing node values in sorted order.
Approach 1: In-order Traversal Using Stack (Time: O(n), Space: O(h))
A Binary Search Tree produces values in sorted order when visited using in-order traversal (left → node → right). Instead of recursion, this approach uses an explicit stack to simulate the traversal. As you iterate through nodes, track the value of the previously visited node. The minimum absolute difference must occur between two adjacent values in the sorted sequence, so compute current.val - prev at each step and update the minimum.
The algorithm repeatedly pushes left children onto the stack, pops the next node to process, then moves to the right subtree. Each node is visited exactly once. This makes the time complexity O(n), where n is the number of nodes. The stack stores at most the height of the tree, giving O(h) auxiliary space. Use this version when you want an iterative solution or when recursion depth might be a concern.
Approach 2: Recursive In-order Traversal (Time: O(n), Space: O(h))
This version performs the same sorted traversal but relies on recursion instead of a manual stack. The recursion explores the left subtree, processes the current node, then explores the right subtree. Maintain two variables across calls: the previously visited value and the global minimum difference. Each time the traversal visits a node, compare it with the previous value and update the minimum difference.
The key insight is identical: in a BST, the smallest difference always occurs between two consecutive values in the sorted in-order sequence. Because each node is visited once, the runtime is O(n). The recursion stack grows up to the tree height, so space complexity is O(h). This version is concise and commonly used in interview explanations when discussing Depth-First Search on trees.
Both approaches rely on the ordering property of a tree structured as a BST. Instead of comparing every pair of nodes, which would take O(n²), you only compare neighbors in the sorted traversal order.
Recommended for interviews: The recursive in-order traversal is the most common explanation because it clearly demonstrates how BST ordering reduces the problem to comparing adjacent values. Interviewers often accept either version, but showing the stack-based implementation proves you understand how recursion works under the hood.
Approach 1: In-order Traversal Using Stack
In this approach, we will perform an in-order traversal of the BST using an explicit stack to store the node values in a sorted manner. As we traverse the tree, we will calculate the minimum difference between consecutive values.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def minDiffInBST(self, root: TreeNode) -> int:
stack, prev_value, min_diff = [], None, float('inf')
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
if prev_value is not None:
min_diff = min(min_diff, current.val - prev_value)
prev_value = current.val
current = current.right
return min_diffimport java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int minDiffInBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
int prevValue = -1;
int minDiff = Integer.MAX_VALUE;
while (!stack.isEmpty() || current != null) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (prevValue >= 0) {
minDiff = Math.min(minDiff, current.val - prevValue);
}
prevValue = current.val;
current = current.right;
}
return minDiff;
}
}#include<iostream>
#include<stack>
#include<limits>
using namespace std;
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) {}
};
int minDiffInBST(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* current = root;
int prevValue = -1;
int minDiff = numeric_limits<int>::max();
while (!stk.empty() || current != nullptr) {
while (current != nullptr) {
stk.push(current);
current = current->left;
}
current = stk.top();
stk.pop();
if (prevValue >= 0) {
minDiff = min(minDiff, current->val - prevValue);
}
prevValue = current->val;
current = current->right;
}
return minDiff;
}function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var minDiffInBST = function(root) {
let stack = [], current = root;
let prevValue = -1, minDiff = Infinity;
while (stack.length > 0 || current !== null) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (prevValue >= 0) {
minDiff = Math.min(minDiff, current.val - prevValue);
}
prevValue = current.val;
current = current.right;
}
return minDiff;
};#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int minDiffInBST(struct TreeNode* root) {
struct TreeNode *stack[10000];
int stackSize = 0;
struct TreeNode *current = root;
int prevValue = -1;
int minDiff = INT_MAX;
while (stackSize > 0 || current != NULL) {
while (current != NULL) {
stack[stackSize++] = current;
current = current->left;
}
current = stack[--stackSize];
if (prevValue >= 0) {
minDiff = (current->val - prevValue < minDiff) ? current->val - prevValue : minDiff;
}
prevValue = current->val;
current = current->right;
}
return minDiff;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int MinDiffInBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
int prevValue = -1;
int minDiff = int.MaxValue;
while (stack.Count > 0 || current != null) {
while (current != null) {
stack.Push(current);
current = current.left;
}
current = stack.Pop();
if (prevValue >= 0) {
minDiff = Math.Min(minDiff, current.val - prevValue);
}
prevValue = current.val;
current = current.right;
}
return minDiff;
}
}The Python solution uses a procedural stack-based in-order traversal to simulate recursive behavior. During the traversal, the minimum absolute difference is calculated between successive node values.
Time Complexity: O(N)
Space Complexity: O(H)
Approach 2: Recursive In-order Traversal
This approach relies on a recursive in-order traversal of the BST to compute the minimum absolute difference. We maintain a global variable to track the smallest difference encountered during traversal.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.prev = None
self.min_diff = float('inf')
def minDiffInBST(self, root: TreeNode) -> int:
def inOrder(node: TreeNode):
if not node:
return
inOrder(node.left)
if self.prev is not None:
self.min_diff = min(self.min_diff, node.val - self.prev)
self.prev = node.val
inOrder(node.right)
inOrder(root)
return self.min_diffclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int minDiff = Integer.MAX_VALUE;
private Integer prevValue = null;
public int minDiffInBST(TreeNode root) {
inOrder(root);
return minDiff;
}
private void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
if (prevValue != null) {
minDiff = Math.min(minDiff, node.val - prevValue);
}
prevValue = node.val;
inOrder(node.right);
}
}#include<iostream>
#include<limits>
using namespace std;
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 {
int minDiff = numeric_limits<int>::max();
int prevValue = -1;
public:
void inOrder(TreeNode* node) {
if (node == nullptr) return;
inOrder(node->left);
if (prevValue >= 0) {
minDiff = min(minDiff, node->val - prevValue);
}
prevValue = node->val;
inOrder(node->right);
}
int minDiffInBST(TreeNode* root) {
prevValue = -1;
minDiff = numeric_limits<int>::max();
inOrder(root);
return minDiff;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var minDiffInBST = function(root) {
let minDiff = Infinity;
let prev = null;
function inOrder(node) {
if (!node) return;
inOrder(node.left);
if (prev !== null) {
minDiff = Math.min(minDiff, node.val - prev);
}
prev = node.val;
inOrder(node.right);
}
inOrder(root);
return minDiff;
};#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int minDiff = INT_MAX;
int prev = -1;
void inOrder(struct TreeNode* node) {
if (node == NULL) return;
inOrder(node->left);
if (prev != -1) {
int diff = node->val - prev;
if (diff < minDiff) minDiff = diff;
}
prev = node->val;
inOrder(node->right);
}
int minDiffInBST(struct TreeNode* root) {
prev = -1;
minDiff = INT_MAX;
inOrder(root);
return minDiff;
}using System;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int? prevValue = null;
private int minDiff = int.MaxValue;
public int MinDiffInBST(TreeNode root) {
InOrder(root);
return minDiff;
}
private void InOrder(TreeNode node) {
if (node == null) return;
InOrder(node.left);
if (prevValue != null) {
minDiff = Math.Min(minDiff, node.val - prevValue.Value);
}
prevValue = node.val;
InOrder(node.right);
}
}In Python, recursive strategy is broken into inner function inOrder to isolate logic from class. This utilizes in-memory numerical comparisons to ensure minimum difference tracking remains accurate and swift.
Time Complexity: O(N)
Space Complexity: O(H)
Approach 3: Inorder Traversal
The problem requires us to find the minimum difference between the values of any two nodes. Since the inorder traversal of a binary search tree is an increasing sequence, we only need to find the minimum difference between the values of two adjacent nodes in the inorder traversal.
We can use a recursive method to implement the inorder traversal. During the process, we use a variable pre to save the value of the previous node. This way, we can calculate the minimum difference between the values of two adjacent nodes during the traversal.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary search tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getMinimumDifference(root: TreeNode | null): number {
let [ans, pre] = [Infinity, -Infinity];
const dfs = (root: TreeNode | null) => {
if (!root) {
return;
}
dfs(root.left);
ans = Math.min(ans, root.val - pre);
pre = root.val;
dfs(root.right);
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getMinimumDifference(root *TreeNode) int {
const inf int = 1 << 30
ans, pre := inf, -inf
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
ans = min(ans, root.Val-pre)
pre = root.Val
dfs(root.Right)
}
dfs(root)
return ans
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn get_minimum_difference(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
const inf: i32 = 1 << 30;
let mut ans = inf;
let mut pre = -inf;
fn dfs(node: Option<Rc<RefCell<TreeNode>>>, ans: &mut i32, pre: &mut i32) {
if let Some(n) = node {
let n = n.borrow();
dfs(n.left.clone(), ans, pre);
*ans = (*ans).min(n.val - *pre);
*pre = n.val;
dfs(n.right.clone(), ans, pre);
}
}
dfs(root, &mut ans, &mut pre);
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| In-order Traversal Using Stack | Time Complexity: O(N) |
| Recursive In-order Traversal | Time Complexity: O(N) |
| Inorder Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-order Traversal Using Stack | O(n) | O(h) | When you prefer an iterative solution or want to avoid recursion depth limits. |
| Recursive In-order Traversal | O(n) | O(h) | Most common interview explanation; concise and easy to implement for BST problems. |
Frequently asked questions
Is Minimum Absolute Difference in BST easy or hard?
Minimum Absolute Difference in BST is classified as an Easy problem on LeetCode. The main concept is recognizing that in-order traversal of a BST produces sorted values, which reduces the problem to comparing adjacent elements.
How to solve Minimum Absolute Difference in BST in O(n)?
Perform an in-order traversal so the BST values are processed in sorted order. Maintain a variable storing the previous node's value and compute the difference with the current node. Update the minimum difference at each step. Since every node is visited once, the algorithm runs in O(n) time.
What is the best approach for Minimum Absolute Difference in BST?
The best approach uses in-order traversal of the Binary Search Tree. In-order traversal outputs node values in sorted order, so the minimum absolute difference must occur between two consecutive values. By tracking the previous node value during traversal, you can compute the difference in O(n) time and O(h) space.
What data structure is used in Minimum Absolute Difference in BST?
The problem uses a Binary Search Tree as the core data structure. The solution typically applies depth-first search with in-order traversal, using either recursion or a stack to process nodes while maintaining the previous value and the current minimum difference.
What is the time complexity of Minimum Absolute Difference in BST?
The optimal solution runs in O(n) time because each node in the tree is visited exactly once during in-order traversal. The space complexity is O(h), where h is the height of the tree, due to the recursion stack or the explicit stack used for traversal.
Minimum Absolute Difference in BST Python or Java solution approach?
Python and Java implementations both follow the same idea: perform an in-order traversal and compare each node's value with the previously visited value. Maintain a global or external variable for the minimum difference. This results in O(n) time and O(h) space for both languages.
Is Minimum Absolute Difference in BST asked at Google, Amazon, or Meta?
Binary Search Tree traversal problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. They test understanding of BST properties, depth-first traversal, and recognizing when sorted order eliminates unnecessary comparisons.