Minimum Absolute Difference in BST

• LeetCode: Minimum Absolute Difference in BST

• Problem:

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

• Note:

There are at least two nodes in this BST.

• Examples:

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

• Analysis:

For a node in BST, the minimun difference of this node is min (the most right leave of left child, the most left leave of right child).

• Code - Java:

/**
 * 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) {
        if (root == null) {
            return 0;
        }
        return helper(root);
    }

    private int helper(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int val = Integer.MAX_VALUE;
        if (root.left != null) {
            TreeNode left = root.left;
            while (left != null && left.right != null) {
                left = left.right;
            }
            val = Math.min(val, root.val - left.val);
        }
        if (root.right != null) {
            TreeNode right = root.right;
            while (right != null && right.left != null) {
                right = right.left;
            }
            val = Math.min(val, right.val - root.val);
        }
        return Math.min(val, Math.min(helper(root.left), helper(root.right)));
    }
}

• Code - C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        return helper(root);
    }

    int helper(TreeNode* root) {
        if (root == NULL) {
            return INT_MAX;
        }
        int val = INT_MAX;
        if (root->left != NULL) {
            TreeNode* left = root->left;
            while (left != NULL && left->right != NULL) {
                left = left->right;
            }
            val = min(val, root->val - left->val);
        }
        if (root->right != NULL) {
            TreeNode* right = root->right;
            while (right != NULL && right->left != NULL) {
                right = right->left;
            }
            val = min(val, right->val - root->val);
        }
        return min(val, min(helper(root->left), helper(root->right)));
    }
};

• Code - Python:

# 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):
    max_int = 2 ** 31 - 1
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        return self.helper(root)

    def helper(self, root):
        if root == None:
            return self.max_int
        val = self.max_int
        if root.left != None:
            left = root.left
            while left != None and left.right != None:
                left = left.right
            val = min(val, root.val - left.val)
        if root.right != None:
            right = root.right
            while right != None and right.left != None:
                right = right.left
            val = min(val, right.val - root.val)
        return min(val, min(self.helper(root.left), self.helper(root.right)))

• Time Complexity: O(N^2), N is the number of nodes

• Space Complexity: O(1)