Largest BST in Binary Tree

Problem

You're given a binary tree. Your task is to find the size of the largest subtree within this binary tree that also satisfies the properties of a Binary Search Tree (BST). The size of a subtree is defined as the number of nodes it contains. (link)

Note: A subtree of the binary tree is considered a BST if for every node in that subtree, the left child is less than the node, and the right child is greater than the node, without any duplicate values in the subtree.

Examples :

Input: root = [5, 2, 4, 1, 3]
Output: 3
Explanation:The following sub-tree is a BST of size 3

Input: root = [6, 7, 3, N, 2, 2, 4]

Output: 3
Explanation: The following sub-tree is a BST of size 3:

Constraints:
1 ≤ number of nodes ≤ 10⁵
1 ≤ node->data ≤ 10⁵

Solution

• Idea:

  • If both the left and right subtrees are already Binary Search Trees (BSTs), the current node can be part of a larger BST if:

    • The largest value in the left subtree is less than the current node.

    • The current node is less than the smallest value in the right subtree.

  • If the current node cannot form a BST with its subtrees, pass the maximum size of the two subtrees.

  • Adjust the min and max values to ensure this node or subtree cannot be considered a BST.

    • For a left child, set the largest value greater than the parent node.

    • For a right child, set the smallest value less than the parent node, breaking the BST property.

  • If a parent node's left or right child is null, return a dummy node that satisfies the BST property.

• Note:

  • If the left subtree is a BST and its largest value is smaller than the parent node, but the right subtree is not a BST, the parent node cannot be included in the left subtree.

  • You cannot simply add the parent node to the left subtree size, as this does not meet the BST definition.

• Summary:

  • Build the BST from the bottom up, including nodes only where they can form a valid BST.

Time - O(n)

Space - O(1)

class Triplet{

    int size;
    int smallest = Integer.MAX_VALUE;
    int largest = Integer.MIN_VALUE;

    Triplet(){}

    Triplet(int size, int smallest, int largest){
        this.size = size;
        this.smallest = smallest;
        this.largest = largest;
    }
}

class Solution {

    private static Triplet getSize(Node root){
        if(root == null){
            return new Triplet();
        }

        Triplet left = getSize(root.left);
        Triplet right = getSize(root.right);

        int smallest;
        int largest;
        if(left.largest < root.data && root.data < right.smallest){
            smallest = Math.min(left.smallest, root.data);
            largest = Math.max(right.largest, root.data);
            return new Triplet(1 + left.size + right.size, smallest, largest);
        }

        smallest = Integer.MIN_VALUE;
        largest = Integer.MAX_VALUE;
        return new Triplet(Math.max(left.size, right.size), smallest, largest);
    }

    static int largestBst(Node root) {
        return getSize(root).size;
    }
}