The O(n) Club: Validate Binary Search Tree—Stop Trusting the Children

The O(n) Club: Validate Binary Search Tree—Stop Trusting the Children

⚡ TL;DR

If you want to validate a Binary Search Tree (BST), don’t just nod along with the immediate children—descendant sabotage is real. Boundaries must be enforced for every node, everywhere. Example of how not to do it in Java:

// Brute-force (and unreliable):
boolean isBST(TreeNode node) {
    if (node == null) return true;
    if (node.left != null && node.left.val >= node.val) return false;
    if (node.right != null && node.right.val <= node.val) return false;
    return isBST(node.left) && isBST(node.right);
}

// This will betray you, just like that ‘quick fix’ you thought was safe in prod.

🧠 How Devs Usually Mess This Up

Most folks run a local background check on just the left and right kids and think the job’s done. But junior misses the criminal cousin living deep in the left subtree, and your BST explodes. Or they’ll gleefully allow duplicate values, because ‘why shouldn’t the left node be equal?’—because LeetCode said so, and so do the rules. Don’t negotiate with tree terrorists.

🔍 What’s Actually Going On

A BST is like a will: it has strict rules, and family drama if they’re broken. Don’t just make sure the direct heirs are in line. Pass down the inheritance boundaries—if you’re in the left branch, you can only inherit less; right branch gets more. These value constraints flow with every recursive hop down the tree, so that sneaky troublemakers (looking at you, third cousin twice removed) can’t cause chaos two levels down.

🛠️ PseudoCode

• Create a function validate(node, min, max), where min/max are the legal boundaries so far.
• If node == null, return true. Even a tumbleweed is a BST.
• If node.val <= min or node.val >= max, return false. Violator caught.
• Recursively check:
  • validate(node.left, min, node.val)
  • validate(node.right, node.val, max)
• Return true if both calls are true. No false positives—unlike your last test suite run.

// Java pseudocode
boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val)
        && validate(node.right, node.val, max);
}

• Always use long for the min/max to survive edge-case apocalypse from min/max integer values.
• No duplicates. No mercy.

💻 The Code

// THE Java solution for BST validation
class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
     private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return validate(node.left, min, node.val)
            && validate(node.right, node.val, max);
    }
}
 // LeetCode-friendly definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Only checking direct children? Prepare for tree betrayal in O(n) time.
• Duplicate values will tank you. The LeetCode gods demand strict BST order—no twinsies.
• Overflow horror. Tree values at Integer.MIN_VALUE or MAX_VALUE? Wrap your boundaries in long or watch your validation crumble.
• Null trees = valid BSTs. Sometimes, the absence of data is the safest data.
• Time/Space Facts: O(n) time (each node visited once), O(h) space (height of the tree)—unless you go wild with non-tail recursion.

🧠 Interviewer Brain-Tattoo

BSTs teach you trust issues for a reason: never trust a node whose ancestors haven’t signed off on its value. (And don’t let them bring their duplicate friends.)