Learning Journal

2/8/2024

Largest BST Subtree - 2nd attempt

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

This is a rather complex recursive problem because of the previous pointer. So, I tried to understand it and I think I just figured out the way to understand complex recursion.

First, you need to convince yourself that it works in some basic cases. Now that you're confident that it works in some basic cases, you don't need to work on it again, just get the result to apply to the more complex case.

For example, with the input [10,5,15,1,8,null,7], let consider the isValidBST function, first you need to convince yourself that it works when root is null.

Well, when root is null, the function return true.

How about when root is the leaf (let say 1). Well, the function will bypass the first if, the second if (because the left subtree is null, and therefore valid), and the third if (because previous is null).

Now, it set previous to 1 and consider the right subtree, which is null, thus, it returns true.

Now, let consider the node 5. The function will bypass the first and second if, in the third if, it checks if the tree is follow the order, if not, it return false. If it does, set the previous to 5 and check the right sub tree, which set the previous to 8 and return true. So the subtree rooted at 5 is a valid BST.

Revised by ChatGPT

This problem, as found on Leetcode, presents a complex scenario that heavily relies on recursion and the use of a previous pointer. To grasp the essence of solving complex recursive problems, it's essential to build confidence in the base and simple cases before tackling more intricate scenarios.

Step-by-Step Breakdown

Base Case Assurance: Initially, ensure that the recursive function behaves as expected in the simplest cases. For the isValidBST function, this means verifying its correctness when the input root is null. In such cases, the BST is inherently valid, so the function returns true.
Leaf Node Analysis: Consider a leaf node, for example, 1. At this level, the function skips the first condition because the node exists. It then bypasses the second condition (isValidBST(root.left)) because the left child is null (and hence, considered a valid BST). The third condition is also skipped since previous is null at this point, indication no prior comparison. The node is set as previous, and its right subtree (null in this case) is evaluated, ultimately returning true confirming the subtree rooted at 1 is a valid BST.
Incremental Complexity: Moving to a node with children, say 5 the function again skips the initial null check. It then recursively checks the left subtree. Given the successful validation of simpler cases (like the leaf node 1), the function proceeds with confidence. The crucial part comes with the comparison involving the previous node to ensure the BST property is maintained. Upon validation, previous is updated to the current node, and the right subtree is examined.
Recursive Explansion: By establishing the validity of smaller units (like individual nodes or leaf-based subtrees), the function recursively builds up to larger structures, ensuring at each step that the BST rules are adhered to. This incremental validation plays a key role in tackling the complexity of determining the largest BST subtree within a given tree.
Leveraging Results for Complex Cases: With confidence in the functionality for basic scenarios, you can then extend these validations to more complex trees. The largestBSTSubtree function utilizes isValidBST to check the validity of the entire tree or its subtrees and employs countNodes to determine the size of valid BSTs, recursively finding the maximum valid BST subtree size.

Key Insight

The essence of understanding and solving complex recursive problems lies in breaking down the problem into simpler, manageable cases. By validating the approach on these simpler cases, you establish a foundation of confidence that allows for the extension of logic to more complex scenarios, ensuring the entire solution is built on a solid, verifiable base.