Minimum Distance Between BST Nodes solution and explanation
Google
9 more videos on this problem
Minimum Distance between BST Nodes - Leetcode 783 - PythonNeetCodeIO · 8:01 · 28K views
2 approaches LeetCode 783. Minimum Distance Between BST Nodes | JSer - JavaScript & AlgorithmJSer · 11:15 · 2K views
Minimum Distance Between BST Nodes | Leetcode 783 | Amazon Google Facebook interview questionSuper Lazy Coder · 6:41 · 2K views
783. Minimum Distance Between BST Nodes | LeetCode Daily ChallengeDeep Tech · 13:57 · 947 views
Leetcode 783 Minimum Distance Between BST Nodes - Amazon Interview QuestionAlgorithmicIQ · 5:55 · 800 views
LeetCode 783 | Minimum Distance Between BST Nodes | In order Traversal | JavaSleepy Cracker · 3:05 · 623 views
Leetcode 783 - Min Distance Between BSTThe Coachable Dev · 5:48 · 506 views
783. Minimum Distance Between BST Nodes - JAVA (Inorder traversal - detailed explanation)Sourin Majumdar · 14:04 · 497 views
LeetCode 783 Minimum Distance Between BST NodesJeevan Kumar - Cracckify · 9:51 · 486 views
783. Minimum Distance Between BST Nodes | JavaScript | DFS | O(n) | LeetCode Daily ChallengeLeetCodeWithMonu · 12:11 · 210 views
The problem
Given the root of a Binary Search Tree (BST), return the minimum 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, 100]. 0 <= Node.val <= 105
Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
Approach overview
Problem Overview: Given the root of a Binary Search Tree (BST), compute the minimum absolute difference between values of any two different nodes. Because of the BST property, an inorder traversal visits nodes in sorted order, which makes it easy to compare adjacent values.
Approach 1: Inorder Traversal (O(n) time, O(h) space)
The key BST property: inorder traversal returns values in ascending order. Instead of comparing every pair of nodes, you only compare each node with the previously visited node during traversal. Keep a variable prev to store the previous value and update the minimum difference using current - prev. Traverse the tree using DFS recursion or an explicit stack. This reduces the problem from pairwise comparisons to a single pass over the sorted sequence of values.
This approach uses a standard Depth-First Search traversal on a Binary Search Tree. The time complexity is O(n) because each node is visited once. Space complexity is O(h), where h is the tree height, due to the recursion stack (O(log n) for balanced trees, O(n) for skewed trees).
Approach 2: Morris Traversal (O(n) time, O(1) space)
Morris Traversal performs inorder traversal without recursion or a stack by temporarily modifying tree pointers. For each node, locate its inorder predecessor (the rightmost node in its left subtree). Create a temporary thread pointing back to the current node so the traversal can return after finishing the left subtree.
While visiting nodes in inorder order, maintain the same prev value and update the minimum difference exactly as in the standard traversal. After processing, restore the tree structure by removing the temporary threads. This approach keeps the O(n) time complexity but reduces auxiliary space to O(1).
Morris traversal is useful when memory constraints matter or when recursion depth could become large. The logic is more complex than the standard DFS approach but eliminates the stack entirely while still leveraging the sorted order property of a Tree that satisfies BST ordering.
Recommended for interviews: The inorder traversal solution is what interviewers typically expect. It directly uses the BST property and is easy to implement with DFS. Mentioning Morris traversal shows deeper understanding of tree traversal techniques and space optimization, but most interviewers prioritize the clear O(n) DFS solution first.
Approach 1: Approach 1: Inorder Traversal
An inorder traversal of a BST yields nodes in non-decreasing order. By performing an inorder traversal, we can collect the values of the nodes in a sorted manner and then iterate through these values to find the minimum difference between successive nodes.
class Solution:
def __init__(self):
self.min_diff = float('inf')
self.prev = None
def minDiffInBST(self, root):
self.inorder(root)
return self.min_diff
def inorder(self, node):
if not node:
return
self.inorder(node.left)
if self.prev is not None:
self.min_diff = min(self.min_diff, node.val - self.prev)
self.prev = node.val
self.inorder(node.right)class Solution {
int minDiff = Integer.MAX_VALUE;
Integer prev = null;
public int minDiffInBST(TreeNode root) {
inorder(root);
return minDiff;
}
public void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (prev != null) {
minDiff = Math.min(minDiff, node.val - prev);
}
prev = node.val;
inorder(node.right);
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* root, int& prev, int& minDiff) {
if (root == NULL) return;
inorder(root->left, prev, minDiff);
if (prev != -1) {
minDiff = min(minDiff, root->val - prev);
}
prev = root->val;
inorder(root->right, prev, minDiff);
}
int minDiffInBST(TreeNode* root) {
int minDiff = INT_MAX;
int prev = -1;
inorder(root, prev, minDiff);
return minDiff;
}var minDiffInBST = function(root) {
let minDiff = Infinity;
let prev = null;
const 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;
};
void inorder(struct TreeNode* root, int* prev, int* minDiff) {
if (!root) return;
inorder(root->left, prev, minDiff);
if (*prev != -1) {
int diff = root->val - *prev;
if (diff < *minDiff) {
*minDiff = diff;
}
}
*prev = root->val;
inorder(root->right, prev, minDiff);
}
int minDiffInBST(struct TreeNode* root) {
int minDiff = INT_MAX;
int prev = -1;
inorder(root, &prev, &minDiff);
return minDiff;
}public class Solution {
private int minDiff = int.MaxValue;
private int? prev = null;
public int MinDiffInBST(TreeNode root) {
Inorder(root);
return minDiff;
}
private void Inorder(TreeNode node) {
if (node == null) return;
Inorder(node.left);
if (prev.HasValue) {
minDiff = Math.Min(minDiff, node.val - prev.Value);
}
prev = node.val;
Inorder(node.right);
}
}Here, we store the minimum difference and the previous node value as instance variables. As we traverse the tree using inorder, we update these instance variables to compute the minimum difference.
Time Complexity: O(N) because each node in the tree is visited exactly once.
Space Complexity: O(H), where H is the height of the tree, due to recursion.
Approach 2: Approach 2: Morris Traversal
The Morris Traversal is an inorder tree traversal technique that uses constant space by reusing the tree structure. It involves temporarily rearranging the tree to allow traversal without explicit stack use.
class Solution:
def minDiffInBST(self, root):
min_diff = float('inf')
prev = None
curr = root
while curr is not None:
if curr.left is None:
if prev is not None:
min_diff = min(min_diff, curr.val - prev)
prev = curr.val
curr = curr.right
else:
pred = curr.left
while pred.right is not None and pred.right != curr:
pred = pred.right
if pred.right is None:
pred.right = curr
curr = curr.left
else:
pred.right = None
if prev is not None:
min_diff = min(min_diff, curr.val - prev)
prev = curr.val
curr = curr.right
return min_diffclass Solution {
public int minDiffInBST(TreeNode root) {
int minDiff = Integer.MAX_VALUE;
int prev = -1;
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
if (prev != -1) {
minDiff = Math.min(minDiff, curr.val - prev);
}
prev = curr.val;
curr = curr.right;
} else {
TreeNode pred = curr.left;
while (pred.right != null && pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
if (prev != -1) {
minDiff = Math.min(minDiff, curr.val - prev);
}
prev = curr.val;
curr = curr.right;
}
}
}
return minDiff;
}
}#include <iostream>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int minDiffInBST(TreeNode* root) {
int minDiff = INT_MAX;
int prev = -1;
TreeNode* curr = root;
while (curr) {
if (!curr->left) {
if (prev != -1) {
minDiff = min(minDiff, curr->val - prev);
}
prev = curr->val;
curr = curr->right;
} else {
TreeNode* pred = curr->left;
while (pred->right && pred->right != curr) {
pred = pred->right;
}
if (!pred->right) {
pred->right = curr;
curr = curr->left;
} else {
pred->right = NULL;
if (prev != -1) {
minDiff = min(minDiff, curr->val - prev);
}
prev = curr->val;
curr = curr->right;
}
}
}
return minDiff;
}var minDiffInBST = function(root) {
let minDiff = Infinity;
let prev = null;
let curr = root;
while (curr) {
if (!curr.left) {
if (prev !== null) {
minDiff = Math.min(minDiff, curr.val - prev);
}
prev = curr.val;
curr = curr.right;
} else {
let pred = curr.left;
while (pred.right !== null && pred.right !== curr) {
pred = pred.right;
}
if (pred.right === null) {
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
if (prev !== null) {
minDiff = Math.min(minDiff, curr.val - prev);
}
prev = curr.val;
curr = curr.right;
}
}
}
return minDiff;
};#include <stdio.h>
#include <limits.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int minDiffInBST(struct TreeNode* root) {
int minDiff = INT_MAX;
int prev = -1;
struct TreeNode* curr = root;
while (curr != NULL) {
if (curr->left == NULL) {
if (prev != -1) {
minDiff = (curr->val - prev < minDiff) ? curr->val - prev : minDiff;
}
prev = curr->val;
curr = curr->right;
} else {
struct TreeNode* pred = curr->left;
while (pred->right != NULL && pred->right != curr) {
pred = pred->right;
}
if (pred->right == NULL) {
pred->right = curr;
curr = curr->left;
} else {
pred->right = NULL;
if (prev != -1) {
minDiff = (curr->val - prev < minDiff) ? curr->val - prev : minDiff;
}
prev = curr->val;
curr = curr->right;
}
}
}
return minDiff;
}public class Solution {
public int MinDiffInBST(TreeNode root) {
int minDiff = int.MaxValue;
int? prev = null;
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
if (prev.HasValue) {
minDiff = Math.Min(minDiff, curr.val - prev.Value);
}
prev = curr.val;
curr = curr.right;
} else {
TreeNode pred = curr.left;
while (pred.right != null && pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
if (prev.HasValue) {
minDiff = Math.Min(minDiff, curr.val - prev.Value);
}
prev = curr.val;
curr = curr.right;
}
}
}
return minDiff;
}
}Python implementation applies Morris Traversal for an efficient in-order walk, using tree pointers for thread simulation rather than auxiliary space.
Time Complexity: O(N) in line with linear node traversal.
Space Complexity: O(1) as no extra storage is required beyond initial variables.
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 minDiffInBST(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 minDiffInBST(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::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn min_diff_in_bst(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 |
|---|---|
| Approach 1: Inorder Traversal | Time Complexity: O(N) because each node in the tree is visited exactly once. Space Complexity: O(H), where H is the height of the tree, due to recursion. |
| Approach 2: Morris Traversal | Time Complexity: O(N) in line with linear node traversal. Space Complexity: O(1) as no extra storage is required beyond initial variables. |
| Inorder Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inorder Traversal (DFS) | O(n) | O(h) | Best general solution. Simple, readable, and expected in most coding interviews. |
| Morris Traversal | O(n) | O(1) | Useful when recursion or stack space must be avoided. More complex but memory efficient. |
Frequently asked questions
Is Minimum Distance Between BST Nodes easy or hard?
Minimum Distance Between BST Nodes is classified as an Easy problem. The main insight is recognizing that inorder traversal of a BST produces sorted values, allowing the minimum difference to be found by comparing adjacent nodes during a single traversal.
Minimum Distance Between BST Nodes Python/Java solution
Python and Java implementations typically perform recursive inorder traversal while tracking a previous node value and the current minimum difference. The logic remains identical across languages: traverse left, process node, update difference, then traverse right. Time complexity stays O(n).
How to solve Minimum Distance Between BST Nodes in O(n)?
Perform an inorder traversal of the BST to process node values in sorted order. Maintain a variable storing the previous node value and compute the difference with the current node. Update the minimum difference each time you visit a node. Since each node is visited once, the algorithm runs in O(n) time.
What is the best approach for Minimum Distance Between BST Nodes?
The best approach uses inorder traversal of the Binary Search Tree. Since inorder traversal produces values in sorted order, the minimum difference must appear between two consecutive nodes in that sequence. Track the previous visited value and update the minimum difference during traversal. This runs in O(n) time with O(h) stack space.
Is Minimum Distance Between BST Nodes asked at Google/Amazon/Meta?
BST traversal problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often ask for minimum difference, kth smallest element, or validating BST properties. This problem tests understanding of inorder traversal and the sorted nature of BST nodes.
What data structure is used in Minimum Distance Between BST Nodes?
The problem uses a Binary Search Tree. The algorithm relies on depth‑first traversal (inorder DFS) to process nodes in sorted order. Some implementations also use a stack for iterative traversal or Morris traversal for constant-space processing.
What is the time complexity of Minimum Distance Between BST Nodes?
The optimal time complexity is O(n) because every node in the BST is visited exactly once during traversal. Space complexity is O(h) for recursive inorder traversal where h is the tree height, or O(1) when using Morris traversal that avoids recursion and extra stacks.