> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-09-2022-530.-minimum-absolute-difference-in-bst.md).

# 04/09/2022 530. Minimum Absolute Difference in BST

530\. Minimum Absolute Difference in BST

730\. Minimum Distance Between BST Nodes 

Fully taking advantage of the fact that it is a BST, we can run an inorder traversal to get an ordered sequence, the intuition is the min diff can only happen between two consecutive nodes in such sequence since none of the node values is negative. The more two nodes are apart, the bigger diff they have.

Method: recursion. Because the inorder of BST is in ascending order. We can make use of this feature to get the difference between each node's val. We set a TreeNode prev = null, when traverse the node, if (prev != null) we can get the difference between curr.val and prev.val. If the prev == null, we can set prev = curr. 

Time O(N)

Space O(h)

```
// Some code
class Solution {
    TreeNode prev = null;
    int result = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return result;
        dfs(root);
        return result;
    }
    private void dfs(TreeNode root){
        if (root == null) return;
        dfs(root.left);
        if (prev != null){
            result = Math.min(result, root.val - prev.val);
        }
        prev = root;
        dfs(root.right);
    }
}
```

```
class Solution {
    public int getMinimumDifference(TreeNode root) {
        // info[0] is prev value in inorder sequence while info[1] holds the min difference
      	int[] info = new int[]{-1, Integer.MAX_VALUE};
        inorder(root, info);
        return info[1];
    }
    
    private void inorder(TreeNode root, int[] info) {
        if (root == null) {
            return;
        }
        inorder(root.left, info);
      	// if the current node has a prev in inorder traversal
        if (info[0] != -1) {
          	// update difference, since it's inorder, root.val is guranteed to be greater than prev in a BST 
            info[1] = Math.min(info[1], root.val - info[0]);
        }
      	// update prev node
        info[0] = root.val;
        inorder(root.right, info);
    }
}
```

Method 2:

iteration. Use stack to simulate the inorder of BST.