Largest BST

Given a binary tree. Find the size of its largest subtree which is a Binary Search Tree.
Note: Here Size equals the number of nodes in the subtree.

Examples :

Input:   1
        /  \
        4   4              
       / \ 
      6   8
Output: 1 
Explanation: There's no sub-tree with size greater than 1 which forms a BST. All the leaf Nodes are the BSTs with size equal to 1.

Input:    6
        /   \
      6      2              
       \    / \
        2  1   3
Output: 3
Explanation: The following sub-tree is a BST of size 3:  2
                                                       /   \
                                                      1     3

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(Height of the BST).

Constraints:
1 ≤ Number of nodes ≤ 10⁵
1 ≤ Data of a node ≤ 10⁶

Approach 01:

class Solution {
public:
    int largestBst(Node* root) {
        return findLargestBST(root).size;
    }

private:
    struct SubtreeInfo {
        bool isBST;
        int size;
        int minValue;
        int maxValue;
        SubtreeInfo(bool isBST, int size, int minValue, int maxValue) 
            : isBST(isBST), size(size), minValue(minValue), maxValue(maxValue) {}
    };

    SubtreeInfo findLargestBST(Node* node) {
        if (!node) {
            return SubtreeInfo(true, 0, INT_MAX, INT_MIN);
        }

        SubtreeInfo leftInfo = findLargestBST(node->left);
        SubtreeInfo rightInfo = findLargestBST(node->right);

        if (leftInfo.isBST && rightInfo.isBST && leftInfo.maxValue < node->data && node->data < rightInfo.minValue) {
            int currentSize = 1 + leftInfo.size + rightInfo.size;
            int currentMin = std::min(leftInfo.minValue, node->data);
            int currentMax = std::max(node->data, rightInfo.maxValue);
            return SubtreeInfo(true, currentSize, currentMin, currentMax);
        }

        return SubtreeInfo(false, std::max(leftInfo.size, rightInfo.size), 0, 0);
    }
};

class Solution:
    def largestBst(self, root):
        def findLargestBST(node):
            if not node:
                return True, 0, float("inf"), float("-inf")
            
            isLeftBST, leftSize, leftMin, leftMax = findLargestBST(node.left)
            isRightBST, rightSize, rightMin, rightMax = findLargestBST(node.right)
            
            if isLeftBST and isRightBST and leftMax < node.data < rightMin:
                currentSize = 1 + leftSize + rightSize
                currentMin = min(leftMin, node.data)
                currentMax = max(node.data, rightMax)
                return True, currentSize, currentMin, currentMax
            return False, max(leftSize, rightSize), 0, 0
        
        return findLargestBST(root)[1]

Time Complexity

• Tree Traversal:

  The function findLargestBST is called recursively for each node in the tree exactly once, leading to a traversal of all \( n \) nodes. Therefore, the time complexity for this traversal is \( O(n) \).

• Overall Time Complexity:

  The overall time complexity of the algorithm is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The auxiliary space required for the recursion stack is proportional to the height of the tree. In the worst case, the height of the tree is \( O(n) \) (for a skewed tree), and in the best case (for a balanced tree), the height is \( O(\log n) \).

• Additional Space:

  Additional space is used for storing the SubtreeInfo structure, but this is constant space for each node, so it doesn’t affect the overall space complexity significantly.

• Overall Space Complexity:

  The overall space complexity is \( O(h) \), where \( h \) is the height of the tree. This could range from \( O(\log n) \) for a balanced tree to \( O(n) \) for a skewed tree.