Skip to content

Minimum Absolute Difference in BST⚓︎

Link

Description⚓︎

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

  • Input: root = [4,2,6,1,3]
  • Output: 1

Example 2:

  • Input: root = [1,0,48,null,null,12,49]
  • Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 10^4].
  • 0 <= Node.val <= 10^5

Solution⚓︎

Recursive Inorder⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int res = INT_MAX;
    TreeNode* prev = nullptr;

    void traversal(TreeNode* root) {
        if (!root) return;
        traversal(root->left);
        if (prev) res = min(res, root->val - prev->val);
        prev = root;
        traversal(root->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return res;
    }
};
  • Time complexity: \(O(n)\):
    • We traverse once over each node of the BST using in-order traversal which takes \(O(n)\) time;
  • Space complexity: \(O(n)\):
    • The in-order traversal is recursive and would take some space to store the stack calls. The maximum number of active stack calls at a time would be the tree's height, which in the worst case would be \(O(n)\) when the tree is a straight line;
    • Note that this space complexity is only for the worst-case scenario, and in the average case we have greatly improved our space complexity since we don't need to create a list to store all the nodes.

Iterative Inorder⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int res = INT_MAX;
        TreeNode* curr = root, * prev = nullptr;
        stack<TreeNode*> stk;
        while (curr || !stk.empty()) {
            if (curr) {
                stk.push(curr);
                curr = curr->left;
            } else {
                TreeNode* t = stk.top();
                stk.pop();
                if (prev) res = min(res, t->val - prev->val);
                prev = t;
                curr = t->right;
            }
        }
        return res;
    }
};