Minimum Distance Between BST Nodes Solution

Problem

Given a binary search tree, find the smallest difference between the values of any two distinct nodes in the tree. Because it's a BST, the tree is already implicitly sorted — this structure is what lets us solve the problem efficiently.

[4,2,6,1,3]

Input: root = [4, 2, 6, 1, 3]
Output: 1
Explanation: The closest pair is any of (1,2), (2,3), or (3,4), each differing by 1.

Intuition

In a BST, an in-order traversal (left → root → right) always visits nodes in strictly ascending order. That means the minimum difference between any two nodes can only exist between values that are adjacent in the sorted sequence — comparing non-adjacent values would always yield a larger gap. So the problem reduces to: traverse in-order, compare each node to the one just before it, and track the smallest gap seen.

Approach 1 — Collect Then Scan

Do a full in-order traversal to build a sorted list of all values, then scan adjacent pairs to find the minimum difference. Straightforward but uses O(n) extra space to store the entire list before comparing.

Run in-order DFS, appending each node's value to a list.
The resulting list is sorted because of BST properties.
Iterate through adjacent pairs (values[i-1], values[i]).
Track the minimum difference seen.
Return it.

1def minDiffInBST(self, root):
2    sorted_values = []
3
4    def inorder(node):
5        if not node:
6            return
7        inorder(node.left)
8        sorted_values.append(node.val)
9        inorder(node.right)
10
11    inorder(root)
12
13    min_diff = float('inf')
14    for i in range(1, len(sorted_values)):
15        min_diff = min(min_diff, sorted_values[i] - sorted_values[i - 1])
16    return min_diff

Time: O(n) — visits every node exactly once.
Space: O(n) — the sorted list holds all n values, plus O(h) recursion stack.

Approach 2 — In-Order with Running Previous (Optimal)

Instead of storing all values, track only the last visited value and update the minimum difference on the fly. This halves the space needed because we never accumulate the full list.

Initialize prev_val = None and min_diff = infinity.
Run in-order DFS.
At each node, if prev_val exists, update min_diff = min(min_diff, node.val - prev_val).
Set prev_val = node.val before returning.
Return min_diff after the traversal completes.

1def minDiffInBST(self, root):
2    self.min_diff = float('inf')
3    self.prev_val = None
4
5    def inorder(node):
6        if not node:
7            return
8        inorder(node.left)
9        if self.prev_val is not None:  # skip comparison on the very first node visited
10            self.min_diff = min(self.min_diff, node.val - self.prev_val)
11        self.prev_val = node.val
12        inorder(node.right)
13
14    inorder(root)
15    return self.min_diff

Time: O(n) — still visits every node once.
Space: O(h) — only the recursion stack; h is tree height (O(log n) balanced, O(n) worst case).

Complexity Summary

Approach	Time	Space	When to use
Collect Then Scan	O(n)	O(n)	When you want simpler, more readable code and memory is not a concern
Running Previous	O(n)	O(h)	Preferred in interviews; saves space and shows understanding of BST properties

Common Mistakes

Comparing all pairs in O(n²) — the BST property makes this unnecessary; in-order traversal produces sorted order, so the minimum gap is always between neighbors, never between distant nodes.
Skipping the prev_val is None guard — the leftmost node has no predecessor; subtracting None/null from its value crashes or produces a wrong result.
Applying a general binary tree strategy — collecting values and then sorting works on any tree, but here the BST guarantees in-order traversal is already sorted, so the extra sort is wasted work.
Using INT_MIN as the C++ sentinel for prevVal — if any node has value 0, the difference 0 - INT_MIN overflows. Use -1 since constraints guarantee non-negative values.
Returning the minimum node value instead of the minimum difference — a common slip when first writing the running-prev version; make sure you're computing current - prev, not just current.

Minimum Distance Between BST Nodes — Solution