Q10: How do you validate whether a Binary Tree is a valid Binary Search Tree (BST)?

Pass dynamic valid range constraints (min and max pointers) recursively down the tree. For a node to be valid, its value must satisfy min < node.val < max. When recurring left, update max = node.val. When recurring right, update min = node.val.

Validate BST Solution

public class ValidateBST {
    public static boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }
    private static boolean validate(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
            return false;
        }
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    }
}

💡 Validates that node values fall within strict minimum and maximum subtree constraints.

Key Takeaways

Use Long pointers or object wrappers for min/max bounds to handle Integer.MIN_VALUE edge cases.
Validates that every left descendant is strictly smaller and right descendant is strictly larger.

Knowledge Check

Why is simply checking node.left.val < node.val && node.right.val > node.val for each node insufficient to validate a BST?

Q10: How do you validate whether a Binary Tree is a valid Binary Search Tree (BST)?

STAY UPDATED WITH BYTES!