Minimum Absolute Difference in BST

Easy

#0515Time: O(N log N), where N is the number of nodes. The tree traversal takes O(N), sorting the list takes O(N log N), and the final pass takes O(N). The sorting step is the bottleneck.Space: O(N) to store the node values in a list. The recursion stack for traversal also contributes up to O(N) in the worst case.

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree Binary Search Tree

Prompt

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, 10⁴].
0 <= Node.val <= 10⁵

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Approaches

3 approaches with complexity analysis and trade-offs.

A more optimized approach is to collect all node values, sort them, and then find the minimum difference between adjacent elements. The minimum difference in a sorted set of numbers will always occur between two consecutive numbers.

Algorithm

Create an empty list values.
Traverse the tree (e.g., using pre-order traversal) and add all node values to the values list.
Sort the values list using Collections.sort().
Initialize minDiff to Integer.MAX_VALUE.
Iterate through the sorted list from the second element (i = 1 to values.size() - 1).
In each iteration, calculate the difference: diff = values.get(i) - values.get(i - 1).
Update minDiff = Math.min(minDiff, diff).
Return minDiff.

Walkthrough

Similar to the brute-force approach, we first traverse the tree to collect all node values into a list. Any traversal order (pre-order, in-order, or post-order) works for this step. Once we have the list of all values, we sort it in ascending order. After sorting, the problem is reduced to finding the minimum difference between any two adjacent elements in the sorted list. We iterate through the sorted list from the second element and calculate the difference between the current element and the previous one. We keep track of the minimum difference found during this single pass.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5/**6 * Definition for a binary tree node.7 * public class TreeNode {8 *     int val;9 *     TreeNode left;10 *     TreeNode right;11 *     TreeNode() {}12 *     TreeNode(int val) { this.val = val; }13 *     TreeNode(int val, TreeNode left, TreeNode right) {14 *         this.val = val;15 *         this.left = left;16 *         this.right = right;17 *     }18 * }19 */20class Solution {21    public int getMinimumDifference(TreeNode root) {22        List<Integer> values = new ArrayList<>();23        collectValues(root, values);24        25        Collections.sort(values);26        27        int minDiff = Integer.MAX_VALUE;28        for (int i = 1; i < values.size(); i++) {29            minDiff = Math.min(minDiff, values.get(i) - values.get(i - 1));30        }31        return minDiff;32    }33 34    private void collectValues(TreeNode node, List<Integer> values) {35        if (node == null) {36            return;37        }38        values.add(node.val);39        collectValues(node.left, values);40        collectValues(node.right, values);41    }42}

Complexity

Time

O(N log N), where N is the number of nodes. The tree traversal takes O(N), sorting the list takes O(N log N), and the final pass takes O(N). The sorting step is the bottleneck.

Space

O(N) to store the node values in a list. The recursion stack for traversal also contributes up to O(N) in the worst case.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Relatively easy to implement.

Cons

Still not optimal as it requires extra space for the list and an O(N log N) sorting step.
It doesn't fully exploit the BST property in real-time; it uses it indirectly by sorting the collected values.

Solutions

Solution

1/** * 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 getMinimumDifference ( 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.

← Previous

Previous problem

Next problem