Recursive C++ solution beat 99.43% with explanation


  • 0

    To find the largest BST subtree, there are two cases:

    • the given tree itself is a BST, then return its total number of nodes.
    • otherwise, the largest BST subtree is in its left or/and right substree(s).

    For case 1, use recursion to check if both subtrees are also BST and also in required value range.
    For case 2, use recursion to find largest BST subtree by design.

        int largestBSTSubtree(TreeNode* r) {
            int numNode;
            if (isBST(r, INT_MIN, INT_MAX, numNode)) return numNode;
            return std::max(largestBSTSubtree(r->left), largestBSTSubtree(r->right));
        }
        
        // helper function to check if a binary tree is BST and also calculates number of nodes if true
        bool isBST(TreeNode* r, int min, int max, int& numNode) {
            if (!r) {
                numNode = 0;
                return true;
            }
            if (r->val < min || r->val > max) return false;
            int leftNode, rightNode;
            bool leftValid = isBST(r->left, min, r->val, leftNode);
            if (!leftValid) return false;
            bool rightValid = isBST(r->right, r->val, max, rightNode);
            if (rightValid) {
                numNode = 1 + leftNode + rightNode;
                return true;
            }
            else return false;
        }
    

  • 1

    There are lots of duplicated check in your code. For example, you check isBST(r->left) when you run isBST(r). But later you check isBST(r-left) again in largestBSTSubtree(r->left).


  • 0

    You are right. Actually, I was also annoyed by my isBST check in my first attempt since it also does recursion on subtrees. I made an improved version to just use a single recursive function. The helper function "myLargestBSTSubtree" also returns the number of nodes in largest BST subtree, but it also calculates node value range and root of desired subtree as side products since they are needed in recursion.

    BTW, the 99.43% beating of first version is probably due to recent OJ upgrade :-)

        int largestBSTSubtree(TreeNode* r) {
            int min, max;
            TreeNode* root;
            return myLargestBSTSubtree(r, min, max, root);
        }
        
        // r: root of given tree
        // min/max: the min/max node values of largest BST subtree
        // root: root of largest BST subtree
        int myLargestBSTSubtree(TreeNode* r, int& min, int& max, TreeNode*& root) {
            min = INT_MAX, max = INT_MIN, root = r;
            if (!r) return 0;
            int minL, minR, maxL, maxR;
            TreeNode* rootL, *rootR;
            int numNodesL = myLargestBSTSubtree(r->left,  minL, maxL, rootL);
            int numNodesR = myLargestBSTSubtree(r->right, minR, maxR, rootR);
            if (r->left == rootL && r->right == rootR && maxL <= r->val && minR >= r->val) {
                min = std::min(minL, r->val); 
                max = std::max(maxR, r->val); 
                root = r; 
                return numNodesL+numNodesR+1;
            } else {
                min = (numNodesL >= numNodesR)? minL : minR; 
                max = (numNodesL >= numNodesR)? maxL : maxR; 
                root = (numNodesL >= numNodesR)? rootL : rootR; 
                return std::max(numNodesL, numNodesR);
            }
        }
    

  • 0
    S

    Correct, but is O(nlogn)


  • 0

    @serendipity0306 Did you mean my original post or the improved one right above your post? The improved version basically does a post-order traversal which costs O(N) time complexity, where Nis the number of nodes in the given binary tree.
    I didn't see why it is O(N*logN)time. Could you please elaborate?


Log in to reply
 

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