Table of contents

Size of the Largest BST in a Binary Tree

Given a binary tree, write a program to find the size of the largest Binary Search Tree (BST) that can be formed from any of its subtrees. The size of a BST is the total number of nodes in that subtree.

Input/Output Examples

plaintext
Example 1:
Input:
       5
      / \
     2   4
    / \
   1   3

Output: 3
Explanation: The largest BST in the tree is:
   2
  / \
 1   3
which has 3 nodes.

Example 2:
Input:
       10
      /  \
     5   15
    / \    \
   1   8    7

Output: 3
Explanation: The largest BST in the tree is:
   5
  / \
 1   8
which has 3 nodes.

Approach to Find the Size of the Largest BST in a Binary Tree

  1. Post-order Traversal:
    • To solve this problem, we need to use post-order traversal (left → right → root) so that we can first compute the information for the left and right subtrees and then use this information to determine whether the current node forms a BST with its left and right subtrees.
  2. For Each Node, We Check the Following:
    • If the current node, along with its left and right subtrees, forms a valid BST.
    • To determine if a subtree is a BST:
      • The left subtree must be a BST, and the maximum value in the left subtree must be less than the current node's value.
      • The right subtree must be a BST, and the minimum value in the right subtree must be greater than the current node's value.
    • If both the left and right subtrees are BSTs and satisfy the conditions above, then the current subtree rooted at the current node is also a BST, and we can calculate its size.
  3. Helper Function:
    • Create a helper function that returns multiple pieces of information for each subtree:
      • Whether it is a BST or not.
      • The size of the largest BST found so far.
      • The minimum and maximum values in the subtree.
  4. Base Case:
    • If the node is NULL, it is a valid BST with size 0, and the minimum value is positive infinity while the maximum value is negative infinity.

C++ Program to Find the Size of the Largest BST in a Binary Tree

cpp
#include <iostream>
#include <climits>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Structure to hold information about each subtree
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) {}
};

// Helper function to find the size of the largest BST
SubtreeInfo largestBSTUtil(TreeNode* root) {
    // Base case: An empty tree is a BST of size 0
    if (root == NULL) {
        return SubtreeInfo(true, 0, INT_MAX, INT_MIN);
    }

    // Recursively find information for the left and right subtrees
    SubtreeInfo leftInfo = largestBSTUtil(root->left);
    SubtreeInfo rightInfo = largestBSTUtil(root->right);

    // Check if the current subtree is a BST
    if (leftInfo.isBST && rightInfo.isBST &&
        leftInfo.maxValue < root->data && root->data < rightInfo.minValue) {

        // Current subtree is a BST, calculate its size
        int size = leftInfo.size + rightInfo.size + 1;
        int minValue = min(leftInfo.minValue, root->data);
        int maxValue = max(rightInfo.maxValue, root->data);

        return SubtreeInfo(true, size, minValue, maxValue);
    }

    // If the current subtree is not a BST, return the largest size found so far
    return SubtreeInfo(false, max(leftInfo.size, rightInfo.size), 0, 0);
}

// Function to find the size of the largest BST in a binary tree
int largestBSTSize(TreeNode* root) {
    return largestBSTUtil(root).size;
}

int main() {
    // Create a sample tree
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(5);
    root->right = new TreeNode(15);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(8);
    root->right->right = new TreeNode(7);

    // Find and print the size of the largest BST
    cout << "Size of the largest BST is: " << largestBSTSize(root) << endl;

    return 0;
}

Java Program to Find the Size of the Largest BST in a Binary Tree

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

// Structure to hold information about each subtree
class SubtreeInfo {
    boolean isBST;
    int size;
    int minValue;
    int maxValue;

    SubtreeInfo(boolean isBST, int size, int minValue, int maxValue) {
        this.isBST = isBST;
        this.size = size;
        this.minValue = minValue;
        this.maxValue = maxValue;
    }
}

public class LargestBSTInBinaryTree {

    // Helper function to find the size of the largest BST
    public static SubtreeInfo largestBSTUtil(TreeNode root) {
        // Base case: An empty tree is a BST of size 0
        if (root == null) {
            return new SubtreeInfo(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        // Recursively find information for the left and right subtrees
        SubtreeInfo leftInfo = largestBSTUtil(root.left);
        SubtreeInfo rightInfo = largestBSTUtil(root.right);

        // Check if the current subtree is a BST
        if (leftInfo.isBST && rightInfo.isBST &&
            leftInfo.maxValue < root.data && root.data < rightInfo.minValue) {

            // Current subtree is a BST, calculate its size
            int size = leftInfo.size + rightInfo.size + 1;
            int minValue = Math.min(leftInfo.minValue, root.data);
            int maxValue = Math.max(rightInfo.maxValue, root.data);

            return new SubtreeInfo(true, size, minValue, maxValue);
        }

        // If the current subtree is not a BST, return the largest size found so far
        return new SubtreeInfo(false, Math.max(leftInfo.size, rightInfo.size), 0, 0);
    }

    // Function to find the size of the largest BST in a binary tree
    public static int largestBSTSize(TreeNode root) {
        return largestBSTUtil(root).size;
    }

    public static void main(String[] args) {
        // Create a sample tree
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(8);
        root.right.right = new TreeNode(7);

        // Find and print the size of the largest BST
        System.out.println("Size of the largest BST is: " + largestBSTSize(root));
    }
}

Python Program to Find the Size of the Largest BST in a Binary Tree

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Structure to hold information about each subtree
class SubtreeInfo:
    def __init__(self, is_bst, size, min_value, max_value):
        self.is_bst = is_bst
        self.size = size
        self.min_value = min_value
        self.max_value = max_value

# Helper function to find the size of the largest BST
def largest_bst_util(root):
    # Base case: An empty tree is a BST of size 0
    if root is None:
        return SubtreeInfo(True, 0, float('inf'), float('-inf'))

    # Recursively find information for the left and right subtrees
    left_info = largest_bst_util(root.left)
    right_info = largest_bst_util(root.right)

    # Check if the current subtree is a BST
    if (left_info.is_bst and right_info.is_bst and
        left_info.max_value < root.data < right_info.min_value):
        # Current subtree is a BST, calculate its size
        size = left_info.size + right_info.size + 1
        min_value = min(left_info.min_value, root.data)
        max_value = max(right_info.max_value, root.data)
        return SubtreeInfo(True, size, min_value, max_value)

    # If the current subtree is not a BST, return the largest size found so far
    return SubtreeInfo(False, max(left_info.size, right_info.size), 0, 0)

# Function to find the size of the largest BST in a binary tree
def largest_bst_size(root):
    return largest_bst_util(root).size

# Example usage
if __name__ == "__main__":
    # Create a sample tree
    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)

    # Find and print the size of the largest BST
    print("Size of the largest BST is:", largest_bst_size(root))
  • Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once to calculate whether it forms a BST or not.
  • Space Complexity: O(h), where h is the height of the tree. This space is required for the recursive call stack. In the worst case, the space complexity can be O(n).

DSA

Related Articles