Leetcode 530. Minimum Absolute Difference in BST

Problem Explanation

In this problem, we're given a binary search tree (BST) in which all nodes contain non-negative values. Our task is to find the smallest absolute difference between the values of any two nodes in the BST.

For example, in the BST given as:

1
2
3   1
4    \
5     3
6    /
7   2

The smallest absolute difference is 1, which is the difference between nodes 1 and 2 (or 2 and 3).

Approach Explanation

We use an Inorder traversal to visit all the nodes of the BST in sorted (ascending) order. During the traversal, we calculate the difference between the current node value and the previous node value, and update our minimum difference if the calculated difference is smaller.

We use a stack data structure to simulate the recursion in the traversal.

Algorithm Steps

1. Initialize a stack
2. Start from the root node, push all nodes along the path to the nearest left leaf node to the stack.
3. Pop up a node from the stack as the current node, calculate the difference between the current node and the previous node. If the difference is less than the minimum difference recorded, update the minimum difference.
4. If the current node has a right child, go to step 2 with the right child.

Solution

Below we've provided the solution implementation in multiple languages.

Python

1
2python
3class Solution(object):
4    def getMinimumDifference(self, root):
5        """
6        :type root: TreeNode
7        :rtype: int
8        """
9        stack, node, prevMin, minDiff = [], root, float('-inf'), float('inf')
10        while stack or node:
11            while node:
12                stack.append(node)
13                node = node.left
14            node = stack.pop()
15            minDiff = min(node.val - prevMin, minDiff)
16            prevMin = node.val
17            node = node.right
18        return minDiff

Java

1
2java
3class Solution {
4    public int getMinimumDifference(TreeNode root) {
5        Stack<TreeNode> stack = new Stack<>();
6        TreeNode node = root, prev = null;
7        int minDiff = Integer.MAX_VALUE;
8        while (!stack.isEmpty() || node != null) {
9            while (node != null) {
10                stack.push(node);
11                node = node.left;
12            }
13            node = stack.pop();
14            if (prev != null) {
15                minDiff = Math.min(minDiff, node.val - prev.val);
16            }
17            prev = node;
18            node = node.right;
19        }
20        return minDiff;
21    }
22}

JavaScript

1
2javascript
3var getMinimumDifference = function(root) {
4    let prev = -1, min = Number.MAX_SAFE_INTEGER;
5    const stack = [];
6    while (stack.length > 0 || root) {
7        while (root) {
8            stack.push(root);
9            root = root.left;
10        }
11        root = stack.pop();
12        if (prev >= 0) {
13            min = Math.min(min, Math.abs(root.val - prev));
14        }
15        prev = root.val;
16        root = root.right;
17    }
18    return min;
19};

C++

1
2cpp
3class Solution {
4public:
5    int getMinimumDifference(TreeNode* root) {
6         int minDiff = INT_MAX;
7         TreeNode* prev = NULL;
8         stack<TreeNode*> nodeStack;
9         while (root != NULL || !nodeStack.empty()) {
10            while (root != NULL) {
11              nodeStack.push(root);
12              root = root->left;
13            }
14            root = nodeStack.top();
15            nodeStack.pop();
16            if (prev != NULL) {
17              minDiff = min(root->val - prev->val, minDiff);
18            }
19            prev = root;
20            root = root->right;
21          }
22        return minDiff;
23    }
24};

C#

1
2csharp
3public class Solution {
4    public int GetMinimumDifference(TreeNode root) {
5        int minDiff = int.MaxValue;
6        TreeNode prev = null;
7        Stack<TreeNode> stack = new Stack<TreeNode>(); 
8        while (root != null || stack.Any()) {
9            while (root != null) {
10                stack.Push(root);
11                root = root.left;
12            }
13            root = stack.Pop();
14            if (prev != null) {
15                minDiff = Math.Min(root.val - prev.val, minDiff);
16            }
17            prev = root;
18            root = root.right;
19        }
20        return minDiff;
21    }
22}

In each of these solutions, we are using a stack to keep track of nodes and their order in the tree, while traversing the tree with an Inorder traversal. Note that the tree's Inorder traversal visits the nodes in ascending order for a BST. We compare each node with its preceding node to calculate and update minimum difference.## Time and Space Complexity Analysis

For all the given solutions in Python, JavaScript, Java, C++ and C#, the time complexity is the same which is O(n), where n is the total number of nodes in the BST. This is because in the worst case, each node in the BST has to be visited and compared once.

The space complexity for the solutions is also O(n) as in the worst case, a stack with n elements is needed to store nodes for comparison. This would be the case in a skewed tree where all nodes have only one child, resulting in longer paths and consequently, larger stack.

However, with a balanced binary tree, the space complexity would approach O(log n), which represents the height of the tree.

Conclusion

Finding the smallest absolute difference in a BST requires understanding the properties of BSTs and how different tree traversal methods can be used. In this problem, Inorder traversal method was used due to the specific property of BSTs where Inorder traversal visits nodes in ascending order.

The Python, JavaScript, Java, C++ and C# solutions presented here all used a stack data structure to record the nodes visited during an Inorder traversal of the BST. By comparing each node with its preceding node, we were able to find and update the minimum difference between any two nodes in the BST.

In conclusion, this problem provided a good example for showcasing how knowledge about specific data structures properties and different traversal methods can be leveraged to solve problems efficiently.