Can the space complexity of a solution using recursive function be O(1)?

Question

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.

Answer 1

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).