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:
[2, 104].0 <= Node.val <= 105Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
The key insight for Minimum Absolute Difference in BST is the ordered nature of a Binary Search Tree. When a BST is traversed using inorder traversal, the node values appear in sorted order. This property allows us to compare only adjacent values in the traversal sequence to find the minimum absolute difference.
Instead of storing the entire sorted list, an efficient approach is to perform a Depth-First Search (DFS) inorder traversal while keeping track of the previous visited node. For each current node, compute the difference with the previous value and update the minimum difference accordingly.
This method works because the smallest difference in a sorted sequence must occur between neighboring elements. The traversal touches each node exactly once, giving a time complexity of O(n). The space complexity is O(h), where h is the tree height due to the recursion or stack used during traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Inorder DFS Traversal with Previous Node Tracking | O(n) | O(h) |
NeetCodeIO
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.
Time Complexity: O(N), where N is the number of nodes. Each node is visited exactly once.
Space Complexity: O(H), where H is the height of the tree, representing the maximum size of the stack.
1#include<stdio.h>
2#include<stdlib.h>
3#include<limits.h>
4
5struct TreeNode {
6 int val;
7
The C solution uses an iterative approach with a stack to perform an in-order traversal. The stack mimics the call stack used in recursion, storing nodes to revisit them in the correct order. The minimum difference is updated whenever a valid consecutive pair is found.
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.
Time Complexity: O(N)
Space Complexity: O(H), due to recursive call stack.
1using System;
2
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);
}
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In a Binary Search Tree, inorder traversal visits nodes in ascending order. This guarantees that the smallest absolute difference will always appear between two consecutive elements in the traversal sequence.
Yes, BST traversal problems are common in technical interviews, including FAANG-style interviews. This question tests understanding of BST properties, inorder traversal, and how to optimize comparisons during tree traversal.
The optimal approach is to perform an inorder traversal of the BST. Since inorder traversal produces sorted values, you only need to compare each node with the previously visited node to compute the minimum difference efficiently.
The BST itself provides the structure needed for the optimal solution. Using recursion or a stack for DFS traversal while tracking the previous value is sufficient, without requiring additional data structures like arrays.
C# adoption introduces nullable types for tracking node values. In this way, each recursion elegantly handles missing values without need for excessive condition checks, exemplifying C#'s language features.