I have solved the 98th problem in leetcode and this is my solution:

class Solution {
public:
    long long pre;
    bool check(TreeNode *node) {
        if(!node) return true;
    
        bool left = check(node->left);
        bool mid = node->val > pre;
        pre = node->val;
        bool right = check(node->right);
    
        return left & mid & right;
    }
    bool isValidBST(TreeNode* root) {
        pre = (long long)INT_MIN - 1;
        return check(root);
    }
};

However, I am not sure if this solution consumes O(n) or O(1) space since someone told me that a recursive function would make use of stack, which makes this solution consume O(n) space.

But in my opinion, pre is not an parameter of a recursive function. Besides, pre's original value won't be needed anymore whenever it is changed since check(node) traverse a tree in in-order and whenever a node's value has been compared with pre, it won't be visited in the future, so it only consume O(1) space.

Please help me to clarify the problem.

CodePudding user response：

You need O(max tree depth) space for the parameters and local variables. For a balanced tree, that's O(log nodes), and for a maximally imbalanced tree, that's O(nodes).

The stack frame for the call to check(parent) has to exist at the same time as the stack frame for it's call check(parent->left) (and similarly check(parent->right)). What you don't need is the stack frame of check(parent->left) to exist at the same time as that of check(parent->right).