Minimum Absolute Difference in BST Solution

Leetcode Solution: Understand and solve Leetcode problem Minimum Absolute Difference in BST(530)

12 September 2020

In this article we’ll be solving the problem: Minimum Absolute Difference in BST. Just like the problem, Convert BST to Greater Tree, this problem also requires a slight modification in a simple Tree Traversal approach along with some knowledge of BST.

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

We’ll be using the following tree as the input to solve the problem:

If we traverse this tree using the In Order Tree Traversal approach then we’ll actually be traversing the tree in a sorted way, i.e., in non-decreasing order. For example, here is the in order tree traversal output of our input:

To solve this problem we’ve to find the Minimum Absolute Difference between any of the two nodes. For a sorted array, the Minimum Absolute Difference will always be between those two elements that are placed next to each other. Now, if we traverse the input Binary Search Tree using the In Order approach, we’ll actually be traversing the sorted array. This way we can keep finding the difference between two consecutive elements and compare it with the minimum absolute difference that we’ve found so far.

Here’s the program to for that:

var minimumDifference int

func getMinimumDifference(root *TreeNode) int {
	minimumDifference = math.MaxInt32
	if root == nil {
		return 0
	}
	inOrder(root, math.MaxInt32)
	return minimumDifference
}

func inOrder(node *TreeNode, lastValue int) int {
	if node.Left != nil {
		lastValue = inOrder(node.Left, lastValue)
	}
	difference := lastValue - node.Val
	if difference < 0 {
		difference = -difference
	}
	if difference < minimumDifference {
		minimumDifference = difference
	}
	lastValue = node.Val
	if node.Right != nil {
		lastValue = inOrder(node.Right, lastValue)
	}
	return lastValue
}

This program is available on GitHub as well. The variable, minimumDifference, will keep the absolute minimum difference and after finding difference between two nodes, we are comparing it with the minimumDifference. We update its value if the current difference is lower.

Loading Comments... Disqus Loader

Minimum Absolute Difference in BST Solution

Leetcode Solution: Understand and solve Leetcode problem Minimum Absolute Difference in BST(530)

Related Pages: