530

530. Minimum Absolute Difference in BST (Easy)

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

 

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [2, 104].
• 0 <= Node.val <= 105

 

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Companies:
Google

Related Topics:
Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

Similar Questions:

• K-diff Pairs in an Array (Medium)

Solution 1. In-order Traversal

// OJ: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int prev = -1, ans = INT_MAX;
        function<void(TreeNode*)> dfs = [&](TreeNode *root) {
            if (!root) return;
            dfs(root->left);
            if (prev != -1) ans = min(ans, root->val - prev);
            prev = root->val;
            dfs(root->right);
        };
        dfs(root);
        return ans;
    }
};