Learning Journal

2/7/2024

Largest BST Subtree

Tags: algorithms leetcode binary_search_tree

let previous:TreeNode | null = null;

const isValidBST = (root:TreeNode | null) : boolean => {
    if(!root) return true;

    if(!isValidBST(root.left)) return false;

    if(previous && previous.val >= root.val) return false;

    previous = root;

    return isValidBST(root.right);
}

const countNodes = (root: TreeNode | null):number => {
    if(!root) return 0;

    return 1 + countNodes(root.left) + countNodes(root.right);
}

const largestBSTSubtree = (root:TreeNode | null):number => {
    if(!root) return 0;

    previous = null;

    if(isValidBST(root)) {
        return countNodes(root);
    }

    return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));   
}let previous:TreeNode | null = null;

const isValidBST = (root:TreeNode | null) : boolean => {
    if(!root) return true;

    if(!isValidBST(root.left)) return false;

    if(previous && previous.val >= root.val) return false;

    previous = root;

    return isValidBST(root.right);
}

const countNodes = (root: TreeNode | null):number => {
    if(!root) return 0;

    return 1 + countNodes(root.left) + countNodes(root.right);
}

const largestBSTSubtree = (root:TreeNode | null):number => {
    if(!root) return 0;

    previous = null;

    if(isValidBST(root)) {
        return countNodes(root);
    }

    return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));   
}

THE PROBLEM

Let me try to explain how it works.

If the root is the binary search tree, you count the nodes of the tree and return it. If it is not, you call the function recursively to count the largestBST on the left subtree and the right subtree. When you reach the bottom (root === null), you return 0;

How do you count? You count the left subtree and then the right subtree, then add 1 for the root. The base case is when root === null.

The heart of the algorithm is to check whether it is a valid BST.

First, you check the left subtree to see if it is a valid BST, if it is not, you just return false. If it is, you need to check if it follows the ascending order, which means the previous node needs to be less than the current node. If it is not, return false. If it is, or you're at the start, you set previous to the current node and then continue to check the right subtree. When you check the right subtree, you do the same thing, which is check the left, check the order, then check the right. If the right is also the BST, it means that the tree rooted at the current node is a BST.

Revised by ChatGPT

This solution aims to identify the largest Binary Search Tree (BST) within a given binary tree. The algorithm consists of three main functions: isValidBST, countNodes, and largestBSTSubtree.

How It Works:

Validating BST: The core of the algorithm lies in determining if a subtree is a valid BST. This is done using the isValidBST function:

The function traverses the tree in an in-order manner (left, root, right).
It checks if the value of the current node is greater than that of the previous node (stored in a global variable previous). If not, the subtree rooted at this node is not a BST, and the function returns false.
The check starts from the leftmost node, ensuring that each node follows the ascending order, crucial for a BST.

Counting Nodes: Once a subtree is confirmed as a BST, the countNodes function calculates its size. It recursively counts the number of nodes in both left and right subtrees and adds one for the root node. The base case occurs when the root is null, where it returns 0.
Finding the Largest BST Subtree: The largestBSTSubtree function orchestrates the process:

It first checks if the entire tree is a BST using isValidBST. If true, it counts the number of nodes using countNodes to find the size of this BST.
If the current subtree is not a BST, the function recursively examines both left and right subtrees to find the largest BST within them. It then returns the size of the largest BST found.
This process ensures that the largest BST, regardless of its position within the original tree, is identified and its size returned.

Summary:

The algorithm efficiently identifies the largest BST within a binary tree by combining validation, counting, and recursive exploration. It leverages in-order traversal to validate BST properties and recursive decomposition to explore all possible subtrees, ensuring comprehensive coverage and accurate identification of the largest BST subtree.