Formatted question description: https://leetcode.ca/all/530.html

530. Minimum Absolute Difference in BST

Level

Easy

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

First obtain the inorder traversal of the binary search tree, which contains all the values in the binary search tree in sorted order. Then calculate absolute differences between each pair of adjacent values in the inorder traversal, and return the minimum absolute difference.

  • /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int getMinimumDifference(TreeNode root) {
            List<Integer> inorderTraversal = inorderTraversal(root);
            int minimumDifference = Integer.MAX_VALUE;
            int size = inorderTraversal.size();
            for (int i = 1; i < size; i++)
                minimumDifference = Math.min(minimumDifference, inorderTraversal.get(i) - inorderTraversal.get(i - 1));
            return minimumDifference;
        }
    
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> inorderTraversal = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (!stack.isEmpty() || node != null) {
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
                TreeNode visitNode = stack.pop();
                inorderTraversal.add(visitNode.val);
                node = visitNode.right;
            }
            return inorderTraversal;
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
    // 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;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.val = None
        self.ans = float("inf")
    
        def inorder(root):
          if not root:
            return
          inorder(root.left)
          if self.val is not None:
            self.ans = min(self.ans, abs(root.val - self.val))
          self.val = root.val
          inorder(root.right)
    
        inorder(root)
        return self.ans
    
    

All Problems

All Solutions