Count Good Nodes in Binary Tree — LC 1448 DFS Carry Pattern

Problem Statement#

Given a binary tree root, a node X is called good if every node on the path from the root to X has a value less than or equal to X.val. In other words, no ancestor on the path is strictly greater than X. Return the number of good nodes.

Constraints:

• The number of nodes is in the range [1, 10^5]
• Each node value is between -10^4 and 10^4

Input:  root = [3,1,4,3,null,1,5]
Output: 4
        Good nodes: 3 (root), 4, 3 (left-left), 5

Input:  root = [3,3,null,4,2]
Output: 3
        Good nodes: 3 (root), 3, 4

Why This Problem Matters#

LeetCode 1448 Count Good Nodes in Binary Tree is among the most asked binary tree interview questions at Microsoft, Meta, Amazon, and Bloomberg. Microsoft has historically tagged it as one of their most frequent 2021-2024 phone screen questions. It tests pure DFS with carried path state — a foundational pattern that appears in dozens of follow-up problems.

What makes 1448 a great interview filter: candidates who instinctively store the entire path in a list (O(n) per node, O(n^2) overall) are easy to distinguish from those who realize a single integer (the running max) suffices. That insight separates O(n^2) thinkers from O(n) thinkers in 30 seconds of conversation.

The pattern transfers directly to "valid sequence" problems, "monotone path" problems, and any tree query where the answer at a node depends only on a path-aggregate, not the full path.

The Core Insight#

A node X is good iff X.val >= max(values on path root -> X excluding X). Maintain a single integer maxSoFar representing the maximum value seen on the current root-to-node path. At each node:

1. If node.val >= maxSoFar, count this node as good.
2. Update maxSoFar = max(maxSoFar, node.val) and recurse into both children.

Because maxSoFar is passed by value (not by reference), each recursive branch sees its own copy — no manual backtracking needed. Initialize with -infinity so the root is always counted as good (no ancestors).

Visual Dry Run#

Tree: [3,1,4,3,null,1,5]

Good count = 4.

Solution (Optimal)#

class Solution:
    def goodNodes(self, root) -> int:
        def dfs(node, max_so_far):
            if not node:
                return 0
            is_good = 1 if node.val >= max_so_far else 0
            new_max = max(max_so_far, node.val)
            return is_good + dfs(node.left, new_max) + dfs(node.right, new_max)
        return dfs(root, float('-inf'))

var goodNodes = function(root) {
    const dfs = (node, maxSoFar) => {
        if (!node) return 0;
        const isGood = node.val >= maxSoFar ? 1 : 0;
        const newMax = Math.max(maxSoFar, node.val);
        return isGood + dfs(node.left, newMax) + dfs(node.right, newMax);
    };
    return dfs(root, -Infinity);
};

Time: O(n) — each node visited once with O(1) work. Space: O(h) — recursion stack proportional to tree height.

Common Mistakes#

• Updating maxSoFar BEFORE the comparison — every node looks good incorrectly.
• Initializing maxSoFar to 0 — fails when all values are negative, missing the root.
• Using strict greater (>) instead of >= — the problem allows ties.
• Storing the whole path and recomputing max — turns O(n) into O(n^2).
• Forgetting BFS would need to attach max per queue entry — DFS is cleaner here.

Interview Tips#

• State the carry-state pattern by name: "DFS pushing the running max as a parameter."
• Confirm the comparison is >= (good means no STRICTLY greater ancestor).
• Note edge case: single-node tree returns 1 because root has no ancestors.
• Mention immutable passing avoids backtracking — clean and bug-resistant.
• Offer iterative version with (node, max_so_far) stack if recursion depth is a concern.

Follow-up Questions#

• Count "bad" nodes instead? Return total_nodes - goodNodes(root).
• Iterative version? Use stack of (node, maxSoFar) tuples; same complexity.
• Strictly increasing path nodes? Change comparison to strict >.
• Path with all nodes good? Track sub-tree booleans; return root if entire subtree qualifies.
• K-th smallest good node? In-order traversal collecting good nodes plus selection.

Key Takeaways#

• LeetCode 1448 is a Medium-difficulty FAANG DFS question heavily asked at Microsoft and Meta.
• Use the DFS carry-state pattern: pass maxSoFar down by value, compare, update, recurse.
• The comparison must be >=, not >, because the definition forbids only STRICTLY greater ancestors.
• Initialize maxSoFar to -infinity so the root is always counted as good.
• Time complexity O(n), space complexity O(h) where h is tree height.
• Storing full paths converts O(n) into O(n^2) — interviewers watch for this anti-pattern.
• The carry-state DFS pattern transfers to LC 113, LC 437, LC 124, and many other tree problems.