The O(n) Club: Count Good Nodes in Binary Trees (And Don’t Bring the Whole Family)

The O(n) Club: Count Good Nodes in Binary Trees (And Don’t Bring the Whole Family)

⚡ TL;DR

How many “good” nodes in a binary tree? Easy: a node is “good” if it’s at least as big as all its ancestors from the root (yes, the root counts—even when it’s a disappointment). DFS, just pass the largest value seen so far—don’t drag your baggage through every branch.
Here’s the gist in Java:

// DFS: checking if each node is a record-breaker
int goodNodes(TreeNode root) {
    return dfs(root, Integer.MIN_VALUE);
}
int dfs(TreeNode node, int maxSoFar) {
    if (node == null) return 0;
    int good = node.val >= maxSoFar ? 1 : 0;
    int nextMax = Math.max(maxSoFar, node.val);
    return good + dfs(node.left, nextMax) + dfs(node.right, nextMax);
}

🧠 How Devs Usually Mess This Up

Ready for a car crash in a binary thicket? Here’s how: compare the node to all other nodes (spoiler—it’s not a popularity contest), or schlep an ancestral suitcase with the entire path. No, you only need the max so far—think MVP, not LinkedIn network. And the “path” is from the root every time, not your neighbor’s weird detour.

🔍 What’s Actually Going On

Pretend you’re on a hike and your ego is fragile. Each time you step on a new node, check if you’re as grand as anyone who came before you. If yes: you’re a “good” node—give yourself a participation trophy. The only thing you need to remember is the meanest value so far. Sibling rivalry? Irrelevant.

🛠️ PseudoCode

• Start at root; call it with the lowest possible value (Integer.MIN_VALUE—yes, that’s a thing).
• At each node:
• If node.val ≥ maxSoFar, it’s “good” (finally, validation!).
• Update maxSoFar via Math.max(node.val, maxSoFar).
• Recurse left and right, dragging the new max along.
• If null, return 0; the ancestors don’t count ghosts.
• Add up: you + left + right. That’s your total ego points.

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
 public class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }
    private int dfs(TreeNode node, int maxSoFar) {
        if (node == null) return 0;
        int isGood = node.val >= maxSoFar ? 1 : 0;
        int updatedMax = Math.max(maxSoFar, node.val);
        return isGood + dfs(node.left, updatedMax) + dfs(node.right, updatedMax);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Comparing across the whole tree? Nope. Only the root-to-here lineage matters—not distant cousins.
• Not updating maxSoFar aggressively? Oops—then counting goes sideways fast.
• Single node? It’s always good—must be nice to have no ancestors to judge you.
• Time? O(n), you can’t skip nodes (unless you bribe the interviewer).
• Space? O(h) for recursion. Gets sketchy if your tree is a tall hipster LinkedList.

🧠 Interviewer Brain-Tattoo

“Stop carrying ancestor baggage. Pass the max, leave the rest. DFS therapy works.”