# Minimum Distance (Difference) Between BST Nodes

`Binary Search Tree`

Given a Binary Search Tree (BST) with the root node

`root`

, return the minimum difference between the values of any two different nodes in the tree.**Example :**

Input:

root = [4,2,6,1,3,null,null]

Output:

1

Explanation:

Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

4

/ \

2 6

/ \

1 3

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

**Note:**

- 1.The size of the BST will be between 2 and
`100`

. - 2.The BST is always valid, each node's value is an integer, and each node's value is different.

**In-order Traversal of BST**output the node value in sorted order; using a global variable prev to store previous value for comparison.

**Complexity Analysis**

- Time Complexity: O(N), where N is the number of nodes in the tree. The complexity comes from the sorting operation.
- Space Complexity:O(N), the size of
`vals`

.

class Solution {

List<Integer> vals;

public int minDiffInBST(TreeNode root) {

vals = new ArrayList();

dfs(root);

int ans = Integer.MAX_VALUE;

for (int i = 0; i < vals.size() - 1; ++i)

ans = Math.min(ans, vals.get(i+1) - vals.get(i));

return ans;

}

public void dfs(TreeNode node) {

if (node == null) return;

dfs(node.left);

vals.add(node.val);

dfs(node.right);

}

}

In a binary search tree, an in-order traversal outputs the values of the tree in order. By remembering the previous value in this order, we could iterate over each possible difference, keeping the smallest one.

**Complexity Analysis**

- Time Complexity: O(N), whereNNis the number of nodes in the tree. We iterate over every node once.
- Space Complexity: O(H), whereHHis the height of the tree. This is the space used by the implicit call stack when calling
`dfs`

.

class Solution {

Integer prev, ans;

public int minDiffInBST(TreeNode root) {

prev = null;

ans = Integer.MAX_VALUE;

dfs(root);

return ans;

}

public void dfs(TreeNode node) {

if (node == null) return;

dfs(node.left);

if (prev != null)

ans = Math.min(ans, node.val - prev);

prev = node.val;

dfs(node.right);

}

}

Minimum Distance Between BST Nodes

Last modified 3yr ago