[LeetCode] Minimum Absolute Difference in BST

Problem: 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:

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

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

Approach: A simple inorder traversal is enough to solve this problem as this tree is BST and inorder traversal will output the values in sorted order. Directly look at the implementation to understand the approach better.

Implementation in C#:

    public int GetMinimumDifference(TreeNode root) 

    {

        if (root == null)

        {

            return 0;

        }

        TreeNode prev = null;

        int minDiff = int.MaxValue;

        this.GetMinDiff(root, ref prev, ref minDiff);

        return minDiff;

    }

    

    private void GetMinDiff(TreeNode node, ref TreeNode prev, ref int minDiff)

    {

        if (node == null)

        {

            return;

        }    

        this.GetMinDiff(node.left, ref prev, ref minDiff);

        if (prev != null)

        {

            minDiff = Math.Min(minDiff, Math.Abs(node.val - prev.val));

        }

        prev = node;

        this.GetMinDiff(node.right, ref prev, ref minDiff);

    }

Complexity: O(n)