space complexity for "divide and conquer"

  • 0

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