Minimum Distance Between BST Nodes
EasyPrompt
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: 1Example 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/
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through all possible pairs of nodes in the tree, calculating the absolute difference of their values, and keeping track of the minimum difference found. It does not utilize the properties of a Binary Search Tree.
Algorithm
- Create an empty list
values. - Define a helper function
collectValuesthat performs a pre-order traversal of the tree and adds each node's value to thevalueslist. - Call
collectValuesstarting from theroot. - Initialize
minDifferencetoInteger.MAX_VALUE. - Use a nested loop to iterate through all pairs of elements in the
valueslist. - For each pair, calculate the absolute difference and update
minDifferenceif the new difference is smaller. - Return
minDifference.
Walkthrough
First, we traverse the entire tree to collect all node values into a list. Any traversal method (pre-order, in-order, post-order) works for this step. After populating the list, we use two nested loops to consider every unique pair of values (values[i], values[j]). For each pair, we calculate the absolute difference abs(values[i] - values[j]). We maintain a variable, minDifference, initialized to a very large value. This variable is updated whenever a smaller difference is found. After checking all pairs, minDifference will hold the minimum difference between any two nodes.
import java.util.ArrayList;import java.util.List; class Solution { public int minDiffInBST(TreeNode root) { List<Integer> values = new ArrayList<>(); collectValues(root, values); int minDifference = Integer.MAX_VALUE; for (int i = 0; i < values.size(); i++) { for (int j = i + 1; j < values.size(); j++) { minDifference = Math.min(minDifference, Math.abs(values.get(i) - values.get(j))); } } return minDifference; } private void collectValues(TreeNode node, List<Integer> values) { if (node == null) { return; } values.add(node.val); collectValues(node.left, values); collectValues(node.right, values); }}Complexity
Time
O(N^2), where N is the number of nodes. The tree traversal takes O(N) time. The nested loops to compare all pairs of values take O(N^2) time. Thus, the overall time complexity is dominated by the nested loops.
Space
O(N). We need O(N) space to store the node values in a list. The recursion stack for the traversal also uses space, up to O(N) in the case of a skewed tree.
Trade-offs
Pros
Simple to understand and implement.
Works for any binary tree, not just a BST.
Cons
Highly inefficient due to the O(N^2) time complexity.
Fails to leverage the crucial property of the input being a Binary Search Tree.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; private int prev ; private int inf = Integer . MAX_VALUE ; public int minDiffInBST ( TreeNode root ) { ans = inf ; prev = inf ; dfs ( root ); return ans ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); ans = Math . min ( ans , Math . abs ( root . val - prev )); prev = root . val ; dfs ( root . right ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.