Largest BST in Binary Tree

Intuition

To find the largest Binary Search Tree (BST) subtree within a binary tree, a brute force approach involves examining each node and verifying if the subtree rooted at that node adheres to BST rules. This means ensuring that all values in the left subtree are less than the node's value and all values in the right subtree are greater. By recursively validating each node's subtree, the size of any valid BST subtree can be determined and compared to find the largest one. The key is to traverse the tree and check each subtree for BST properties, keeping track of the largest valid subtree found.

Approach

Define a function isValidBST that checks if a given subtree rooted at a node is a valid BST by performing a recursive traversal with range constraints.
Initialize a variable maxSize to 0 to keep track of the maximum size of any valid BST subtree found. Recursively traverse each node of the given binary tree.
At each node, use the isValidBST function to check if the subtree rooted at that node is a valid BST. If it is, calculate the size of this subtree and update maxSize if this size is larger than the current maxSize.
After traversing all nodes, return maxSize, which will hold the size of the largest BST subtree found.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Helper function to validate BST and get the size of the subtree.
    tuple<int, bool, int, int> isBSTAndSize(TreeNode* node, int minValue, int maxValue) {
        // Base case: if node is nullptr, it is a valid BST of size 0.
        if (!node) {
            return make_tuple(0, true, INT_MAX, INT_MIN);
        }

        // Recursively check the left and right subtrees.
        auto [leftSize, isLeftBST, leftMin, leftMax] = isBSTAndSize(node->left, minValue, node->data);
        auto [rightSize, isRightBST, rightMin, rightMax] = isBSTAndSize(node->right, node->data, maxValue);

        // Check if the current node is a valid BST node.
        if (isLeftBST && isRightBST && leftMax < node->data && node->data < rightMin) {
            // Current subtree is a valid BST, calculate its size.
            int size = leftSize + rightSize + 1;
            // Return size, isBST, min value, and max value for the current subtree.
            return make_tuple(size, true, min(node->data, leftMin), max(node->data, rightMax));
        } else {
            // Current subtree is not a valid BST, return the size of the largest valid BST found so far.
            return make_tuple(max(leftSize, rightSize), false, INT_MIN, INT_MAX);
        }
    }

    int largestBST(TreeNode* root) {
        // Initialize the function to call
        return get<0>(isBSTAndSize(root, INT_MIN, INT_MAX));
    }
};

// Main method to demonstrate usage
int main() {
    // Example binary tree
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);

    Solution sol;
    cout << sol.largestBST(root) << endl;  // Output: 3

    // Additional test case
    TreeNode* root2 = new TreeNode(10);
    root2->left = new TreeNode(5);
    root2->right = new TreeNode(15);
    root2->left->left = new TreeNode(1);
    root2->left->right = new TreeNode(8);
    root2->right->right = new TreeNode(7);

    cout << sol.largestBST(root2) << endl;  // Output: 3 (The subtree 5-1-8 is the largest BST)

    
}
/**
 * Definition for a binary tree node.
 */
public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class Solution {
    // Helper class to store information about a subtree
    class BSTInfo {
        int size;
        boolean isBST;
        int min;
        int max;
        
        BSTInfo(int size, boolean isBST, int min, int max) {
            this.size = size;
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    // Helper function to validate BST and get the size of the subtree.
    private BSTInfo isBSTAndSize(TreeNode node, int minValue, int maxValue) {
        // Base case: if node is null, it is a valid BST of size 0.
        if (node == null) {
            return new BSTInfo(0, true, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        // Recursively check the left and right subtrees.
        BSTInfo left = isBSTAndSize(node.left, minValue, node.data);
        BSTInfo right = isBSTAndSize(node.right, node.data, maxValue);

        // Check if the current node is a valid BST node.
        if (left.isBST && right.isBST && left.max < node.data && node.data < right.min) {
            // Current subtree is a valid BST, calculate its size.
            int size = left.size + right.size + 1;
            // Return size, isBST, min value, and max value for the current subtree.
            return new BSTInfo(size, true, Math.min(node.data, left.min), Math.max(node.data, right.max));
        } else {
            // Current subtree is not a valid BST, return the size of the largest valid BST found so far.
            return new BSTInfo(Math.max(left.size, right.size), false, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
    }

    public int largestBST(TreeNode root) {
        // Initialize the function to call
        return isBSTAndSize(root, Integer.MIN_VALUE, Integer.MAX_VALUE).size;
    }

    // Main method to demonstrate usage
    public static void main(String[] args) {
        // Example binary tree
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        Solution sol = new Solution();
        System.out.println(sol.largestBST(root));  // Output: 3

        // Additional test case
        TreeNode root2 = new TreeNode(10);
        root2.left = new TreeNode(5);
        root2.right = new TreeNode(15);
        root2.left.left = new TreeNode(1);
        root2.left.right = new TreeNode(8);
        root2.right.right = new TreeNode(7);

        System.out.println(sol.largestBST(root2));  // Output: 3 (The subtree 5-1-8 is the largest BST)
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def largestBST(self, root):
        # Helper function to validate BST and get the size of the subtree.
        def isBSTAndSize(node, minValue, maxValue):
            # Base case: if node is None, it is a valid BST of size 0.
            if not node:
                return (0, True, float('inf'), float('-inf'))

            # Recursively check the left and right subtrees.
            leftSize, isLeftBST, leftMin, leftMax = isBSTAndSize(node.left, minValue, node.data)
            rightSize, isRightBST, rightMin, rightMax = isBSTAndSize(node.right, node.data, maxValue)

            # Check if the current node is a valid BST node.
            if isLeftBST and isRightBST and leftMax < node.data < rightMin:
                # Current subtree is a valid BST, calculate its size.
                size = leftSize + rightSize + 1
                # Return size, isBST, min value, and max value for the current subtree.
                return (size, True, min(node.data, leftMin), max(node.data, rightMax))
            else:
                # Current subtree is not a valid BST, return the size of the largest valid BST found so far.
                return (max(leftSize, rightSize), False, float('-inf'), float('inf'))

        # Initialize the function to call
        return isBSTAndSize(root, float('-inf'), float('inf'))[0]

# Main method to demonstrate usage
if __name__ == "__main__":
    # Example binary tree
    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)

    sol = Solution()
    print(sol.largestBST(root))  # Output: 3

    # Additional test case
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(15)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(8)
    root.right.right = TreeNode(7)

    print(sol.largestBST(root))  # Output: 3 (The subtree 5-1-8 is the largest BST)
/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Helper function to validate BST and get the size of the subtree.
    isBSTAndSize(node, minValue, maxValue) {
        // Base case: if node is null, it is a valid BST of size 0.
        if (!node) {
            return { size: 0, isBST: true, min: Infinity, max: -Infinity };
        }

        // Recursively check the left and right subtrees.
        const left = this.isBSTAndSize(node.left, minValue, node.data);
        const right = this.isBSTAndSize(node.right, node.data, maxValue);

        // Check if the current node is a valid BST node.
        if (left.isBST && right.isBST && left.max < node.data && node.data < right.min) {
            // Current subtree is a valid BST, calculate its size.
            const size = left.size + right.size + 1;
            // Return size, isBST, min value, and max value for the current subtree.
            return { size: size, isBST: true, min: Math.min(node.data, left.min), max: Math.max(node.data, right.max) };
        } else {
            // Current subtree is not a valid BST, return the size of the largest valid BST found so far.
            return { size: Math.max(left.size, right.size), isBST: false, min: -Infinity, max: Infinity };
        }
    }

    largestBST(root) {
        // Initialize the function to call
        return this.isBSTAndSize(root, -Infinity, Infinity).size;
    }
}

// Main method to demonstrate usage
const main = () => {
    // Example binary tree
    const root = new TreeNode(2);
    root.left = new TreeNode(1);
    root.right = new TreeNode(3);

    const sol = new Solution();
    console.log(sol.largestBST(root));  // Output: 3

    // Additional test case
    const root2 = new TreeNode(10);
    root2.left = new TreeNode(5);
    root2.right = new TreeNode(15);
    root2.left.left = new TreeNode(1);
    root2.left.right = new TreeNode(8);
    root2.right.right = new TreeNode(7);

    console.log(sol.largestBST(root2));  // Output: 3 (The subtree 5-1-8 is the largest BST)
};

// Run the main method
main();

Complexity Analysis

Time Complexity : O(N*N) , where N is the number of nodes in the Binary Tree. O(N) to traverse through each node in the tree and for each node, the validation ot check whether its subtree is a valid BST takes O(N) time hence the overall time complexity is O(N * N).

Space Complexity O(1)as the there no additional space required for storing variables or data structures.

Intuition

A more efficient method to find the largest Binary Search Tree (BST) subtree within a binary tree involves traversing the tree and simultaneously verifying if each subtree is a BST. By adopting a bottom-up recursive approach, it’s possible to traverse the tree efficiently. For each node, the minimum value, maximum value, size of the BST, and whether it is a BST can be determined based on its children’s information. This approach allows for updating and maintaining the size of the largest BST subtree found during the traversal.

Approach

Define a NodeValue class to store the following information about each subtree:
- minNode: Minimum value of the subtree.
- maxNode: Maximum value of the subtree.
- maxSize: Maximum size of the BST encountered so far.
Implement a helper function largestBSTSubtreeHelper that takes the root as input and recursively gathers information (minNode, maxNode, and maxSize) for each subtree.
- The NodeValue information for the current node is updated based on the left and right subtree properties. Specifically, the left subtree’s maximum node should be less than the current node and the right subtree’s minimum node should be greater than the current node.
- If the current subtree satisfies the BST property, update the size of the node (maxSize) as the sum of maxSize from the left subtree, maxSize from the right subtree, and 1.
- If the current subtree is not a BST, carry forward the current maxSize but set minNode to int min and maxNode to int max.
Return the maxSize of the largest BST subtree found.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Helper class to store information about a subtree.
    struct NodeValue {
        int minNode, maxNode, maxSize;
        NodeValue(int minNode, int maxNode, int maxSize) : minNode(minNode), maxNode(maxNode), maxSize(maxSize) {}
    };

    // Helper function to recursively find the largest BST subtree.
    NodeValue largestBSTSubtreeHelper(TreeNode* node) {
        // Base case: if the node is null, return a default NodeValue.
        if (!node) {
            return NodeValue(INT_MAX, INT_MIN, 0);
        }

        // Recursively get values from the left and right subtrees.
        NodeValue left = largestBSTSubtreeHelper(node->left);
        NodeValue right = largestBSTSubtreeHelper(node->right);

        // Check if the current node is a valid BST node.
        if (left.maxNode < node->data && node->data < right.minNode) {
            // Current subtree is a valid BST.
            return NodeValue(
                min(node->data, left.minNode),
                max(node->data, right.maxNode),
                left.maxSize + right.maxSize + 1
            );
        }

        // Current subtree is not a valid BST.
        return NodeValue(INT_MIN, INT_MAX, max(left.maxSize, right.maxSize));
    }

    int largestBST(TreeNode* root) {
        // Initialize the recursive process and return the size of the largest BST subtree.
        return largestBSTSubtreeHelper(root).maxSize;
    }
};

int main() {
    // Example binary tree
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);

    Solution sol;
    cout << sol.largestBST(root) << endl;  // Output: 3

    // Additional test case
    TreeNode* root2 = new TreeNode(10);
    root2->left = new TreeNode(5);
    root2->right = new TreeNode(15);
    root2->left->left = new TreeNode(1);
    root2->left->right = new TreeNode(8);
    root2->right->right = new TreeNode(7);

    cout << sol.largestBST(root2) << endl;  // Output: 3 (The subtree 5-1-8 is the largest BST)

    return 0;
}
/**
 * Definition for a binary tree node.
 */
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class Solution {
    // Helper class to store information about a subtree.
    class NodeValue {
        int minNode, maxNode, maxSize;
        NodeValue(int minNode, int maxNode, int maxSize) {
            this.minNode = minNode;
            this.maxNode = maxNode;
            this.maxSize = maxSize;
        }
    }

    // Helper function to recursively find the largest BST subtree.
    private NodeValue largestBSTSubtreeHelper(TreeNode node) {
        // Base case: if the node is null, return a default NodeValue.
        if (node == null) {
            return new NodeValue(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }

        // Recursively get values from the left and right subtrees.
        NodeValue left = largestBSTSubtreeHelper(node.left);
        NodeValue right = largestBSTSubtreeHelper(node.right);

        // Check if the current node is a valid BST node.
        if (left.maxNode < node.data && node.data < right.minNode) {
            // Current subtree is a valid BST.
            return new NodeValue(
                Math.min(node.data, left.minNode),
                Math.max(node.data, right.maxNode),
                left.maxSize + right.maxSize + 1
            );
        }

        // Current subtree is not a valid BST.
        return new NodeValue(Integer.MIN_VALUE, Integer.MAX_VALUE, Math.max(left.maxSize, right.maxSize));
    }

    public int largestBST(TreeNode root) {
        // Initialize the recursive process and return the size of the largest BST subtree.
        return largestBSTSubtreeHelper(root).maxSize;
    }
}

class Main {
    // Main method to demonstrate usage
    public static void main(String[] args) {
        // Example binary tree
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        Solution sol = new Solution();
        System.out.println(sol.largestBST(root));  // Output: 3

        // Additional test case
        TreeNode root2 = new TreeNode(10);
        root2.left = new TreeNode(5);
        root2.right = new TreeNode(15);
        root2.left.left = new TreeNode(1);
        root2.left.right = new TreeNode(8);
        root2.right.right = new TreeNode(7);

        System.out.println(sol.largestBST(root2));  // Output: 3 (The subtree 5-1-8 is the largest BST)
    }
}
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    # Helper class to store information about a subtree.
    class NodeValue:
        def __init__(self, minNode, maxNode, maxSize):
            self.minNode = minNode
            self.maxNode = maxNode
            self.maxSize = maxSize

    # Helper function to recursively find the largest BST subtree.
    def largestBSTSubtreeHelper(self, node):
        # Base case: if the node is null, return a default NodeValue.
        if not node:
            return self.NodeValue(float('inf'), float('-inf'), 0)

        # Recursively get values from the left and right subtrees.
        left = self.largestBSTSubtreeHelper(node.left)
        right = self.largestBSTSubtreeHelper(node.right)

        # Check if the current node is a valid BST node.
        if left.maxNode < node.data < right.minNode:
            # Current subtree is a valid BST.
            return self.NodeValue(
                min(node.data, left.minNode),
                max(node.data, right.maxNode),
                left.maxSize + right.maxSize + 1
            )

        # Current subtree is not a valid BST.
        return self.NodeValue(float('-inf'), float('inf'), max(left.maxSize, right.maxSize))

    def largestBST(self, root):
        # Initialize the recursive process and return the size of the largest BST subtree.
        return self.largestBSTSubtreeHelper(root).maxSize

# Main method to demonstrate usage
if __name__ == "__main__":
    # Example binary tree
    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)

    sol = Solution()
    print(sol.largestBST(root))  # Output: 3

    # Additional test case
    root2 = TreeNode(10)
    root2.left = TreeNode(5)
    root2.right = TreeNode(15)
    root2.left.left = TreeNode(1)
    root2.left.right = TreeNode(8)
    root2.right.right = TreeNode(7)

    print(sol.largestBST(root2))  # Output: 3 (The subtree 5-1-8 is the largest BST)
/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

// Define NodeValue class separately
class NodeValue {
    constructor(minNode, maxNode, maxSize) {
        this.minNode = minNode;
        this.maxNode = maxNode;
        this.maxSize = maxSize;
    }
}

class Solution {
    // Helper function to recursively find the largest BST subtree.
    largestBSTSubtreeHelper(node) {
        // Base case: if the node is null, return a default NodeValue.
        if (!node) {
            return new NodeValue(Infinity, -Infinity, 0);
        }

        // Recursively get values from the left and right subtrees.
        let left = this.largestBSTSubtreeHelper(node.left);
        let right = this.largestBSTSubtreeHelper(node.right);

        // Check if the current node is a valid BST node.
        if (left.maxNode < node.data && node.data < right.minNode) {
            // Current subtree is a valid BST.
            return new NodeValue(
                Math.min(node.data, left.minNode),
                Math.max(node.data, right.maxNode),
                left.maxSize + right.maxSize + 1
            );
        }

        // Current subtree is not a valid BST.
        return new NodeValue(-Infinity, Infinity, Math.max(left.maxSize, right.maxSize));
    }

    largestBST(root) {
        // Initialize the recursive process and return the size of the largest BST subtree.
        return this.largestBSTSubtreeHelper(root).maxSize;
    }
}

// Main method to demonstrate usage
const main = () => {
    // Example binary tree
    const root = new TreeNode(2);
    root.left = new TreeNode(1);
    root.right = new TreeNode(3);

    const sol = new Solution();
    console.log(sol.largestBST(root));  // Output: 3

    // Additional test case
    const root2 = new TreeNode(10);
    root2.left = new TreeNode(5);
    root2.right = new TreeNode(15);
    root2.left.left = new TreeNode(1);
    root2.left.right = new TreeNode(8);
    root2.right.right = new TreeNode(7);

    console.log(sol.largestBST(root2));  // Output: 3 (The subtree 5-1-8 is the largest BST)
};

// Run the main method
main();

Complexity Analysis

Time Complexity :O(N), where N is the number of nodes in the Binary tree as we traverse through all the nodes in the tree. The information update for each nodes takes constant time hence the overall time complexity is O(N) as the tree is traversed once.

Space Complexity : O(N) , where N is number of nodes in the Binary Tree as for each node we store additional information using a struct class whose new object is initialised.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code