algoadvance

Leetcode 530. Minimum Absolute Difference in BST

Problem Statement

Given a Binary Search Tree (BST), write a function that returns the minimum absolute difference between the values of any two nodes in the tree.

Clarifying Questions

1. Input Format: What is the structure of the input?
   • You are given the root node of a BST.
2. Node Values: Are all node values unique?
   • Yes, in a typical BST, all node values are unique.
3. Size of the Tree: How large can the tree be?
   • The tree can have up to 10^4 nodes.
4. Node Values Range: What is the range of node values?
   • Node values can be in the range [-10^5, 10^5].

Strategy

1. In-order Traversal: Since an in-order traversal of a BST will give a sorted list of values, the minimum absolute difference would occur between two consecutive elements in this sorted list.

2. Keep Track of Differences: Traverse the tree in an in-order manner and keep track of the previous node’s value to compute the difference with the current node’s value.

3. Update the Minimum Difference: Continuously update the minimum difference encountered during traversal.

Code

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int min_diff = INT_MAX;
        int prev_val = -1;   // Indicator for non-existent previous value
        inOrderTraversal(root, prev_val, min_diff);
        return min_diff;
    }

private:
    void inOrderTraversal(TreeNode* node, int &prev_val, int &min_diff) {
        if (!node) return;

        // Traverse left subtree
        inOrderTraversal(node->left, prev_val, min_diff);

        // Process current node
        if (prev_val != -1) {
            min_diff = min(min_diff, node->val - prev_val);
        }
        prev_val = node->val;

        // Traverse right subtree
        inOrderTraversal(node->right, prev_val, min_diff);
    }
};

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the BST. We visit each node exactly once during the in-order traversal.
• Space Complexity: O(h), where h is the height of the tree. This is the space used by the recursion stack. In the worst case (skewed tree), this could be O(n). In the best case (balanced tree), it would be O(log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?