C++ 7 lines, O(n) run-time O(h) memory


  • 14
    V

    In-order traversal of BST yields sorted sequence. So, we just need to subtract the previous element from the current one, and keep track of the minimum. We need O(1) memory as we only store the previous element, but we still need O(h) for the stack.

    void inorderTraverse(TreeNode* root, int& val, int& min_dif) {
        if (root->left != NULL) inorderTraverse(root->left, val, min_dif);
        if (val >= 0) min_dif = min(min_dif, root->val - val);
        val = root->val;
        if (root->right != NULL) inorderTraverse(root->right, val, min_dif);
    }
    int getMinimumDifference(TreeNode* root) {
        auto min_dif = INT_MAX, val = -1;
        inorderTraverse(root, val, min_dif);
        return min_dif;
    }
    

    Another solution with the member variables (6 lines):

    class Solution {
        int min_dif = INT_MAX, val = -1;
    public:
    int getMinimumDifference(TreeNode* root) {
        if (root->left != NULL) getMinimumDifference(root->left);
        if (val >= 0) min_dif = min(min_dif, root->val - val);
        val = root->val;
        if (root->right != NULL) getMinimumDifference(root->right);
        return min_dif;
    }
    

  • 0
    A

    In the second line, why the C++ can call the inorderTraverse funtion like a void function?


  • 2
    V

    @Allent51 inorderTraverse should be a void function (I have updated the code). I was using the return value as a shortcut, but it actually does not make it shorter. I also posted another solution that uses member variables (6 lines of code). You can see that the only purpose of the the return there is to send the value of the member back to the caller (my original solution was sort of a hybrid of those two).


  • 1
    P

    @votrubac
    Great solution. However it doesn't work for certain cases

    What if all the values are negative or zero?
    "if (val >=0)" creates problem and above code is not working in that case

    e.g. [-1564,-1434,-3048,-1,null,null,-3184]

    Slight modification in your solution:
    (however, there can be better modification)

    class Solution {
    int min_dif = INT_MAX, val = 0;
    bool visited = false;
    public:
    int getMinimumDifference(TreeNode* root) {
    if (root->left != NULL)
    getMinimumDifference(root->left);

    //val is assigned at least once
    if(visited)
    {
    min_dif = min(min_dif, root->val - val);
    }

    val = root->val; 
    visited = true;
    
    if (root->right != NULL) 
        getMinimumDifference(root->right);
        
    return min_dif;
    }
    

    };

    I've requested to add these test cases


  • 1
    L

    @pjain4 The question mentioned "non-negative values".


  • 1
    A

    @Allent51 C++ allows it. The return value will be just ignored, or destroyed if it is an object with no reference.


Log in to reply
 

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