Recursive solution with explanation, O(n) run time and O(1) memory, in C++


  • 1
    T

    The idea is that the minimum absolute difference will only be between two consecutive nodes in an inorder traversal, because doing an inorder traversal on a BST gives a sorted list of elements.

    So, we maintain one variable for the previously seen value, and another variable for the minimum difference seen so far, and update them accordingly. the variable prev starts with the value -1, and min starts with INT_MAX, which is updated when a new lower minimum is found. prev is updated when we see the first leaf (because that will be the first element visited during an inorder traversal.

    /**
     * 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 {
        int prev = -1;
        int min = INT_MAX;
        void recGetMinDiff(TreeNode *root){
            if(!root)
            return;
            
            recGetMinDiff(root->left);
            
            int diff;
            if(prev == -1){
                prev = root->val;
            }
            else{
                diff = fabs(root->val - prev);
                if(min > diff)
                min = diff;
                prev = root->val;
            }
            
            recGetMinDiff(root->right);
        }
        
    public:
        int getMinimumDifference(TreeNode* root) {
            recGetMinDiff(root);
            return min;
        }
    };
    

  • 0
    X

    @tamhankar Not O(1) space


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.