> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/trees/minimum-distance-difference-between-bst-nodes.md).

# Minimum Distance (Difference) Between BST Nodes

`Binary Search Tree`

**Almost** **same as** [**Minimum Absolute Difference in BST**](https://leetcode.com/problems/minimum-absolute-difference-in-bst/)

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.

## Solution

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

<https://leetcode.com/problems/minimum-distance-between-bst-nodes/solution/>

### Approach #1: Write to Array <a href="#approach-1-write-to-array-accepted" id="approach-1-write-to-array-accepted"></a>

**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`.

```java
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);
    }
}
```

### Approach #2: In-Order Traversal <a href="#approach-2-inorder-traversal-accepted" id="approach-2-inorder-traversal-accepted"></a>

> 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`.

```java
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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trees/minimum-distance-difference-between-bst-nodes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.