530.md

530. Minimum Absolute Difference in BST

Description

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary search tree (BST) reversely with Depth-First Search (DFS) algorithm
 * ensures the traversal values are sorted in descending order
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    "use strict";
    let min = -1;
    let preVal = 0;
    function dfs(node) {
        if (node) {
            dfs(node.right);
            let val = Math.abs(node.val-preVal);
            preVal = node.val;
            if (min === -1 || min > val) {
                min = val;
            }
            dfs(node.left);
        }
    }
    dfs(root);
    return min;
};