The blog for Design Patterns, Linux, HA and Myself!

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

- All Elements in Two Binary Search Trees Solution
- Construct Binary Search Tree From Preorder Traversal Solution
- Maximum Binary Tree Solution
- Sum of Nodes With Even Valued Grandparent Solution
- Deepest Leaves Sum Solution
- Symmetric Tree or Mirror Tree Solution
- Diameter of Binary Tree Solution
- Binary Tree Paths Solution
- Cousins in Binary Tree Solution
- Sum of Left Leaves Solution
- Same Tree or Equal Tree Solution
- Minimum Absolute Difference in BST Solution
- Construct String From Binary Tree Solution - Leetcode
- Two Sum IV - Input is a BST Solution - Leetcode
- Convert BST to Greater Tree Solution - Leetcode
- Convert Sorted Array to Binary Search Tree Solution
- Average of Levels in Binary Tree Solution
- Leaf Similar Trees Solution - Leetcode
- Sum of Root to Leaf Binary Numbers - Leetcode
- Univalued Binary Tree - Leetcode
- Maximum Depth of N Ary Tree - Leetcode
- Increasing Order Search Tree - Leetcode
- Merge Two Binary Trees Solution
- Range Sum of BST - Leetcode