Minimum Absolute Difference in BST Problem

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.

OR

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.

Examples

Example 1:

graph TB;
    4 --- 2 & 6;
    2 --- 1 & 3;
  
1
2
3

Input: root = [4,2,6,1,3]
Output: 1
Explanation: Difference between 2 and 1.

Example 2:

graph TB;
    1 --- 0 & 48;
    48 --- 12 & 49;
  
1
2
3

Input: root = [1,0,48,null,null,12,49]
Output: 1
Explanation: Difference between 49 and 48.

Solution

Method 1 - Inorder Traversal - Two Pass

One way can be we do the inorder traversal, and get the list from it in sorted order, and now compare the difference between 2 elements in the array, and return the min value.

Complexity

  • ⏰ Time complexity: O(n) where n is tree size
  • 🧺 Space complexity: O(n), assuming recursion stack and sorted array

Method 2 - Inorder Traversal

Instead of creating the list first, and then find the difference, we can actually track previous node, and calculate the diff with current node in inorder traversal. We also track, the min value and return the min value in the end.

To sum up:

  1. Perform an in-order traversal of the BST to get a sorted list of node values.
  2. Calculate the minimum difference between consecutive values in this sorted list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {

	private Integer prev = null;
	private int minDiff = Integer.MAX_VALUE;
	
	public int minDiffInBST(TreeNode root) {
		inOrderTraversal(root);
		return minDiff;
	}

	private void inOrderTraversal(TreeNode node) {
		if (node == null) {
			return;
		}

		// In-order traversal: left -> root -> right
		inOrderTraversal(node.left);

		// Process current node: update minimum difference
		if (prev != null) {
			minDiff = Math.min(minDiff, node.val - prev);
		}

		prev = node.val;

		inOrderTraversal(node.right);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class Solution {

	private Integer prev = null;
	private int minDiff = Integer.MAX_VALUE;
	
	public int minDiffInBST(TreeNode root) {
		if (root.left != null) {
			minDiffInBST(root.left);
		}
		if (prev != null) {
			minDiff = Math.min(minDiff, root.val - prev);
		}
		if (root.right != null) {
			minDiffInBST(root.right);
		}
		return minDiff;
	}
}

Complexity

  • ⏰ Time complexity: O(n) where n is tree size
  • 🧺 Space complexity: O(h), assuming recursion stack