Blogs Hub

by Sumit Chourasia | Oct 07, 2020 | Category :coding | Tags : algorithm binary-tree data-structure easy leetcode tree

Minimum Absolute Difference in BST - Tree - Easy - LeetCode

Minimum Absolute Difference in BST - Tree - Easy - LeetCode

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.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    int min = int.MaxValue;
    int? prev = null;
    public int GetMinimumDifference(TreeNode root) {
        InOrder(root);
        return min;
    }
    
    private void InOrder(TreeNode root){
        if(root == null){
            return;
        }
        
        InOrder(root.left);
        if(prev!=null){
            min = Math.Min(Math.Abs(root.val-(int)prev),min);
        }
        prev = root.val;
        InOrder(root.right);
    }
}

Time Complexity: O(n)

Space Complexity: O(1)