Learning Journal

2/9/2024

Largest BST Subtree - 3rd attempt

Tags: algorithms leetcode binary_search_tree

let prev:TreeNode|null = null;

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

    prev = null;
    
    if(isValidBST(root)) return countNodes(root);

    const largestR = largestBSTSubtree(root.right);
    const largestL = largestBSTSubtree(root.left);

    return Math.max(largestR, largestL);
    
}

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

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

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

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

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

    prev = root;

    return isValidBST(root.right);
}let prev:TreeNode|null = null;

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

    prev = null;
    
    if(isValidBST(root)) return countNodes(root);

    const largestR = largestBSTSubtree(root.right);
    const largestL = largestBSTSubtree(root.left);

    return Math.max(largestR, largestL);
    
}

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

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

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

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

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

    prev = root;

    return isValidBST(root.right);
}

THE PROBLEM

Some insights I gained during this attempt:

You need to set prev pointer back to null before calling isValidBST in largestBSTSubtree, because you are at the beginning of the new recursive search. In isValidBST, you will go all the way to the left, reach null, return true, then go back to the leftmost node, set prev to that node, then go to the right.
The reason that you need to check if prev is null before comparing its val to the current node in the condition if(prev && prev.val >= root.val) is that we can not guarantee the left node is always available. If root is the leftmost node, there is no left node, thus the function return true at the first condition without assigning prev to any node. So, if there is no prev, it means the current node is at the beginning of the sequence, which also mean that the condition if(prev && prev.val >= root.val) should return true, because it is still the valid BST tree so far.

Revised by ChatGPT

While working on the "Largest BST Subtree" challenge, several key insights emerged that were crucial for developing an effective solution. This challenge requires identifying the largest subtree within a given binary tree that is also a valid Binary Search Tree (BST). The solution involves recursive traversal and validation of BST properties. Below are refined insights from the attempt:

Resetting the prev Pointer: It's imperative to reset the prev pointer to null at the start of each new recursive search within the largestBSTSubtree function. This reset ensures that when isValidBST begins its traversal, it treats the current subtree independently of previous checks. Without resetting, prev might retain a value from a previous subtree check, leading to incorrect comparisons.
Purpose of Checking prev Before Comparison: The condition if(prev && prev.val >= root.val) safeguards against incorrect comparisons when prev is null. This scenario occurs at the very start of the traversal, where there's no previous node to compare with. The initial null state of prev signifies the beginning of a sequence (or the leftmost node in a subtree), ensuring that the comparison logic is only applied when there's a valid previous node. This check is crucial for maintaining the BST invariant, which requires each node to be greater than all nodes in its left subtree and less than all nodes in its right subtree.

ADDITIONAL CONTEXT AND CLARIFICATIONS:

Traversal Order and BST Validation: The isValidBST function uses in-order traversal (left, root, right) to validate the BST properties. This order ensures that nodes are visited in a non-decreasing sequence, allowing for the comparison of each node with its immediate predecessor (tracked by prev). If any node violates the BST condition (i.e., it is not greater than its predecessor), the function immediately returns false.
Recursive Subtree Exploration: The largestBSTSubtree function explores all possible subtrees recursively, comparing the size of valid BST subtrees found in the left and right children of the current node. This approach guarantees that the largest BST subtree in identified, whether it is rooted at the current node (if the current subtree is a valid BST) or located in one of its descendant subtrees.