Largest BST Subtree

// A class to capture information about a subtree
class SubtreeData {
public:
    int minVal, maxVal, treeSize;
    
    SubtreeData(int minVal, int maxVal, int treeSize) {
        this->minVal = minVal;
        this->maxVal = maxVal;
        this->treeSize = treeSize;
    }
};

class Solution {
public:
    SubtreeData helper(TreeNode* node) {
        // Base case: empty subtree
        if (!node) {
            return SubtreeData(INT_MAX, INT_MIN, 0);
        }
        
        // Recursively get the subtree data from the left and right child
        auto leftSubtree = helper(node->left);
        auto rightSubtree = helper(node->right);
        
        // Validate the BST properties at this node
        if (leftSubtree.maxVal < node->val && node->val < rightSubtree.minVal) {
            // Node is a valid root for BST
            return SubtreeData(min(node->val, leftSubtree.minVal), max(node->val, rightSubtree.maxVal), 
                            leftSubtree.treeSize + rightSubtree.treeSize + 1);
        }
        
        // If not a BST, pass up a disrupted range
        return SubtreeData(INT_MIN, INT_MAX, max(leftSubtree.treeSize, rightSubtree.treeSize));
    }
    
    int findLargestBSTSubtree(TreeNode* root) {
        return helper(root).treeSize;
    }
};

This C++ code defines a solution for finding the largest Binary Search Tree (BST) subtree within a given binary tree. It involves a robust approach using class-based techniques and recursion to explore and evaluate subtrees in terms of BST validity and size, and then determine the largest BST subtree. Here’s an overview of how the code accomplishes this:

• The code defines two classes: SubtreeData and Solution.
• SubtreeData class holds three variables: minVal, maxVal, and treeSize, essential for capturing the minimum value, maximum value, and size of the subtree, respectively.
• The helper function in the Solution class recursively examines each node, determining whether the subtree rooted at that node meets BST conditions. This function:
  • Checks if the value at the current node is greater than the maximum value of the left subtree and less than the minimum value of the right subtree. If true, it treats the current node as the root of a valid BST subtree and computes the total size of this subtree.
  • If it doesn’t meet BST conditions, it returns a disrupted range signaling an invalid BST.
• findLargestBSTSubtree utilizes the helper function to start the recursive validation and size determination from the root.

Overall, it cleverly combines structural tree properties analysis and recursive descent to find and measure valid BSTs within a larger binary tree, efficiently identifying the largest BST subtree by size.

// Each node contains the minimal, maximal values and the size of the largest BST
class BSTValues {
    public int maxVal, minVal, maxSize;
    
    BSTValues(int minVal, int maxVal, int maxSize) {
        this.maxVal = maxVal;
        this.minVal = minVal;
        this.maxSize = maxSize;
    }
};

class Solution {
    public BSTValues findLargestBST(TreeNode node) {
        // For a null node, the min value is positive infinity, and the max value is negative infinity.
        if (node == null) {
            return new BSTValues(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }
        
        // Get the BST values for the left and right subtrees.
        BSTValues leftBST = findLargestBST(node.left);
        BSTValues rightBST = findLargestBST(node.right);
        
        // If current node makes a valid BST with the subtrees
        if (leftBST.maxVal < node.val && node.val < rightBST.minVal) {
            // Node is consistent with BST rules
            return new BSTValues(
                Math.min(node.val, leftBST.minVal),
                Math.max(node.val, rightBST.maxVal),
                leftBST.maxSize + rightBST.maxSize + 1
            );
        }
        
        // Return invalid range if not a BST
        return new BSTValues(
            Integer.MIN_VALUE,
            Integer.MAX_VALUE,
            Math.max(leftBST.maxSize, rightBST.maxSize)
        );
    }
    
    public int largestBSTSubtree(TreeNode root) {
        return findLargestBST(root).maxSize;
    }
}

The solution summary for the problem "Largest BST Subtree" in Java involves determining the largest Binary Search Tree (BST) that can be formed within a given binary tree. The implemented Java code defines a class BSTValues to store the essential attributes needed to track the boundaries and size of potential BSTs: minimum value, maximum value, and size of the subtree.

Here's how the underlying logic operates:

1. When encountering a null node, the algorithm returns a BSTValues instance with initialized values: maximum possible integer for minimum value, minimum possible integer for maximum value, and zero for size. This handles the base case of an empty subtree.

2. Recursive calls are made to find the largest BSTs within the left and right child subtrees of the current node.

3. After obtaining the results from left and right child subtrees, the current node's value is compared against the maximum value of the left subtree and the minimum value of the right subtree. This step checks whether adding the current node to either subtree still maintains the BST properties.

4. If the current node can be added to form a larger BST comprising its left and right children, a new BSTValues instance is created with updated boundaries and size. The minimum boundary is updated to the smallest value between the node's value and the left subtree's minimum. Similarly, the maximum boundary is updated to the largest value between the node's value and the right subtree's maximum. The size is the total size of both subtrees plus one (including the current node).

5. If the current node cannot maintain BST properties when connected with either subtree, the algorithm returns a BSTValues instance representing an invalid BST range but carries the maximum size found in either the left or right subtrees.

6. Ultimately, the root of the tree is passed to this method, and the maximum size of the largest BST found is returned.

The approach effectively uses a divide-and-conquer strategy with recursion, efficiently determining the largest BST in the tree by examining each node and deciding whether it can act as the root of a BST by considering the properties of its left and right subtrees. This solution is compact yet robust, leveraging the properties of BSTs and the concept of recursion to simplify the problem-solving process.

class TreeNodeValue {
    constructor(lowest, highest, size) {
        this.lowest = lowest;
        this.highest = highest;
        this.size = size;
    }
};

let findLargestBST = node => {
    // Check if current node is null, indicating an empty subtree.
    if (!node) {
        return new TreeNodeValue(Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER, 0);
    }
    
    // Recursively calculate for left and right subtrees.
    let leftSubtree = findLargestBST(node.left);
    let rightSubtree = findLargestBST(node.right);
    
    // Validate BST property.
    if (leftSubtree.highest < node.val && node.val < rightSubtree.lowest) {
        // If BST checks passed.
        return new TreeNodeValue(Math.min(node.val, leftSubtree.lowest), Math.max(node.val, rightSubtree.highest), 
                                 leftSubtree.size + rightSubtree.size + 1);
    }
    
    // If BST checks fail, report back impossible min and max values.
    return new TreeNodeValue(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, 
                             Math.max(leftSubtree.size, rightSubtree.size));
}

let findLargestBSTSubtree = root => {
    return findLargestBST(root).size;
};

The JavaScript solution provided tackles the problem of finding the largest Binary Search Tree (BST) within a given binary tree. The approach uses a custom class TreeNodeValue to maintain essential information about each subtree: its lowest value, highest value, and size (node count).

• The process begins with the utility function findLargestBST, which recursively investigates each node and its subtrees:

  • Base Case: If the current node is null, it returns a TreeNodeValue instance conveying it as an empty subtree.
  • Recursive Case: It computes the largest BST for the left and right children of the current node.
  • BST Validation: Establishes if the current node forms a BST with its children based on their values.
  • If valid, a new TreeNodeValue gets returned aggregating the size and updating bounds. If invalid, it propagates the larger subtree size upwards while marking bounds as contradictory, indicating a non-BST scenario.

• Subsequently, findLargestBSTSubtree, the main function, simply invokes findLargestBST starting from the root and retrieves the size of the largest BST.

This method efficiently determines the largest BST's size within a binary tree using postorder traversal—comparing, combining, and returning subtree details optimally. This ensures each subtree is visited and its BST validity checked once, optimizing performance by eliminating repeated calculations.

Remember:

• Define a root node to operate on the larger function, findLargestBSTSubtree.
• The tree's structure and node values affect the performance and correctness; ensure node values are set correctly to reflect valid BST properties for accurate results.

# Updated class and function names for equivalent behavior and different syntax
class TreeNodeInfo:
    def __init__(self, min_val, max_val, size):
        self.min_val = min_val
        self.max_val = max_val
        self.size = size

class Solution:
    def helper_find_largest_bst(self, node):
        if not node:
            return TreeNodeInfo(float('inf'), float('-inf'), 0)

        left_info = self.helper_find_largest_bst(node.left)
        right_info = self.helper_find_largest_bst(node.right)

        if left_info.max_val < node.val < right_info.min_val:
            return TreeNodeInfo(min(node.val, left_info.min_val), max(node.val, right_info.max_val), 
                                left_info.size + right_info.size + 1)

        return TreeNodeInfo(float('-inf'), float('inf'), max(left_info.size, right_info.size))

    def findLargestBST(self, root: Optional[TreeNode]) -> int:
        return self.helper_find_largest_bst(root).size

This Python solution identifies the largest Binary Search Tree (BST) subtree within a given binary tree. A BST is defined with the convention that the keys in the left subtree are less than the root node, and the keys in the right subtree are greater than the root node.

The code consists of two classes:

• TreeNodeInfo: This class holds information about a subtree, including its minimum and maximum values, and its size.
• Solution: This class contains two methods.

The method helper_find_largest_bst(node) performs the core logic:

• If the current node is None, it returns a TreeNodeInfo object indicating that there is no subtree.
• It recursively calculates the largest BST properties for both left and right subtrees.
• If the current node can be the root of a BST given the conditions from its left and right children, a new TreeNodeInfo object is created with updated boundaries and size.
• If one of the conditions fails, the function returns the TreeNodeInfo with updated attributes to signal that the current subtree cannot form a valid BST.

findLargestBST(root) serves as a public interface that invokes helper_find_largest_bst and returns the size attribute from the TreeNodeInfo, which represents the size of the largest BST found.

Overall, the algorithm insightfully utilizes recursive traversal and dynamic programming principles to isolate and compute the size of the largest BST, effectively managing edge cases and ensuring optimal performance through well-coordinated state tracking between recursive calls.