space complexity for "divide and conquer"


  • 0
    N

    Hi,
    Below is straightforward divide&conquer. Is the space complexity O(logN) ?
    lc cleanbook says it's O(N) but without any explanation. I believe O(n) is for skewed tree, just like singly linked list . However do we really care for this ?

    Could anyone weigh in here. Thanks a lot

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            return validBST(root, NULL, NULL);
        }
        
        bool validBST(TreeNode* root, TreeNode* maxNode, TreeNode* minNode) {
            if (root == NULL) return true;
            if (maxNode && root->val >= maxNode->val) return false;
            if (minNode && root->val <= minNode->val) return false;
            return validBST(root->left, root, minNode) && validBST(root->right, maxNode, root);
        }
    };
    

Log in to reply
 

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