Count Good Nodes in Binary Tree (LeetCode 1448)
You're given a binary tree root. Call a node X good when no node on the path from the root down to X has a value greater than X's own value.
Count how many nodes in the tree qualify as good.
Worked Examples
root = [3,1,4,3,null,1,5]4root = [3,3,null,4,2]32 is not good: its path is 3 -> 3 -> 2, and 3 is greater than 2. The other three nodes are good.root = [1]1⚖️Formal Constraints & Bounds
The number of nodes in the binary tree is in the range
[1, 105].Each node's value is between
[-104, 104].
Core Insight
Carrying path maxima down the call stack provides O(1) local evaluation without back-tracking.
Real-World Scenario & Production Applications
Hierarchical access control validation (inheriting highest privilege level along an organizational tree).
Step-by-Step Execution Trace Table
| Node | Path Max on Entry | Node.val >= Max? | Is Good? | Next Max for Children |
|---|---|---|---|---|
| 3 (root) | 3 | 3 >= 3 (True) | Yes (1) | 3 |
| 1 | 3 | 1 >= 3 (False) | No (0) | 3 |
| 4 | 3 | 4 >= 3 (True) | Yes (1) | 4 |
| 5 | 4 | 5 >= 4 (True) | Yes (1) | 5 |
root = [3,1,4,3,null,1,5]4| Node | Path Max on Entry | Node.val >= Max? | Is Good? | Next Max for Children |
|---|---|---|---|---|
| 3 (root) | 3 | 3 >= 3 (True) | Yes (1) | 3 |
| 1 | 3 | 1 >= 3 (False) | No (0) | 3 |
| 4 | 3 | 4 >= 3 (True) | Yes (1) | 4 |
| 5 | 4 | 5 >= 4 (True) | Yes (1) | 5 |
| 1 | def dfs(node, max_so_far): |
| 2 | if not node: |
| 3 | return 0 |
| 4 | is_good = 1 if node.val >= max_so_far else 0 |
| 5 | new_max = max(max_so_far, node.val) |
| 6 | return is_good + dfs(node.left, new_max) + dfs(node.right, new_max) |
| 7 | return dfs(root, float('-inf')) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This archetype flips the direction of information flow from the ones before it: instead of children reporting answers up to their parent, the parent hands context down to its children.
🥾 The Analogy: Hiking and Tracking Your Personal Best Altitude
Imagine hiking down from a mountain's root, tracking only one number as you go: the highest altitude you've reached so far on this specific path. At every new point, you compare your current altitude to that personal-best. If you're at or above it, this point counts as "good" — nothing earlier on your path was ever higher — and your personal-best updates itself if you've just set a new record. You never need to remember the entire path behind you, only the single running maximum.
🔑 The Key Idea in the Code
max_so_far is a parameter passed down into each recursive call — the opposite direction from maxDepth's left/right values flowing up. Each node only ever needs the single running maximum handed to it by its parent; it never needs to inspect the full root-to-node path directly.
Mutating global max across sibling branches: Passing a mutable reference or global variable for
max_valleaks the maximum seen in the left subtree into the right subtree traversal. Always passmax_valby value down the call stack.Updating running max too late: If you evaluate
node.val >= max_val, remember to updatenew_max = max(max_val, node.val)before passing to child recursions.Strictly greater vs greater-or-equal: A node is 'good' if its value is greater than OR EQUAL to the maximum on the path from root. Using strict
>drops valid nodes.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement calls a node good when nothing on the path from the root down to it is larger: whether a node counts depends only on the values above it, the Top-Down DFS signal.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
At each node: is_good = 1 if node.val >= max_so_far else 0, then both children get new_max = max(max_so_far, node.val), and the node returns is_good plus its children's counts.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: start
max_so_farat-inf(orroot.val), never at 0, since values can be negative.Compare with
>=, not>: a node equal to the path maximum is good. On[3,3,null,4,2]the second 3 counts and the answer is 3;>returns 2.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Top-Down DFS. Whether a node is good depends only on the values above it, so instead of looking back up the tree I carry the largest value seen so far down as an argument, max_so_far. At each node I compare: if its value is at least max_so_far, it's good. Then I pass the larger of the two to both children and add up the counts they return. Because the value travels as an argument, each call has its own copy, so the left subtree's changes never leak into the right one, and nothing needs undoing on the way back. The trap is the starting value: I start at minus infinity, not zero, because values can be negative and the root must always count. I also compare with greater-or-equal, since a tie with the path maximum is still good. Each node is visited once, so it's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Pre-order DFS passes down the maximum value seen along the path from root. If node.val >= max_so_far, increments good count and updates max_so_far. Each node visited once.
O(H) recursion stack
Call stack depth equals tree height H.
T(N) = O(N)
Derivation Progression
new_max = max(max_so_far, node.val)
Propagates maximum value down each branch in O(1) per frame.
is_good = 1 if node.val >= max_so_far else 0
Tests good node condition in constant time.
∑_{v} 1 = N ⟹ O(N)
Visits all N nodes once.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack depth
O(1) Scalar counter
O(1) Integer count
Boundary Best / Worst Cases
time, space.
time, space.
time, space.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "count good nodes", "no nodes with a value greater than X on path from root". Whether a node counts depends on the path above it: Top-Down DFS, passing max_so_far down each branch.
, values in . Time budget is linear time, space stack frames.
LeetCode allows nodes, so a chain is calls deep, far past CPython's default recursion limit of 1000: walk with an explicit stack of (node, max_so_far) pairs instead.
Count Good Nodes in Binary Tree (LeetCode 1448)
You're given a binary tree root. Call a node X good when no node on the path from the root down to X has a value greater than X's own value.
Count how many nodes in the tree qualify as good.
Worked Examples
root = [3,1,4,3,null,1,5]4root = [3,3,null,4,2]32 is not good: its path is 3 -> 3 -> 2, and 3 is greater than 2. The other three nodes are good.root = [1]1⚖️Formal Constraints & Bounds
The number of nodes in the binary tree is in the range
[1, 105].Each node's value is between
[-104, 104].
Core Insight
Carrying path maxima down the call stack provides O(1) local evaluation without back-tracking.
Real-World Scenario & Production Applications
Hierarchical access control validation (inheriting highest privilege level along an organizational tree).
Step-by-Step Execution Trace Table
| Node | Path Max on Entry | Node.val >= Max? | Is Good? | Next Max for Children |
|---|---|---|---|---|
| 3 (root) | 3 | 3 >= 3 (True) | Yes (1) | 3 |
| 1 | 3 | 1 >= 3 (False) | No (0) | 3 |
| 4 | 3 | 4 >= 3 (True) | Yes (1) | 4 |
| 5 | 4 | 5 >= 4 (True) | Yes (1) | 5 |
root = [3,1,4,3,null,1,5]4| Node | Path Max on Entry | Node.val >= Max? | Is Good? | Next Max for Children |
|---|---|---|---|---|
| 3 (root) | 3 | 3 >= 3 (True) | Yes (1) | 3 |
| 1 | 3 | 1 >= 3 (False) | No (0) | 3 |
| 4 | 3 | 4 >= 3 (True) | Yes (1) | 4 |
| 5 | 4 | 5 >= 4 (True) | Yes (1) | 5 |
| 1 | def dfs(node, max_so_far): |
| 2 | if not node: |
| 3 | return 0 |
| 4 | is_good = 1 if node.val >= max_so_far else 0 |
| 5 | new_max = max(max_so_far, node.val) |
| 6 | return is_good + dfs(node.left, new_max) + dfs(node.right, new_max) |
| 7 | return dfs(root, float('-inf')) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This archetype flips the direction of information flow from the ones before it: instead of children reporting answers up to their parent, the parent hands context down to its children.
🥾 The Analogy: Hiking and Tracking Your Personal Best Altitude
Imagine hiking down from a mountain's root, tracking only one number as you go: the highest altitude you've reached so far on this specific path. At every new point, you compare your current altitude to that personal-best. If you're at or above it, this point counts as "good" — nothing earlier on your path was ever higher — and your personal-best updates itself if you've just set a new record. You never need to remember the entire path behind you, only the single running maximum.
🔑 The Key Idea in the Code
max_so_far is a parameter passed down into each recursive call — the opposite direction from maxDepth's left/right values flowing up. Each node only ever needs the single running maximum handed to it by its parent; it never needs to inspect the full root-to-node path directly.
Mutating global max across sibling branches: Passing a mutable reference or global variable for
max_valleaks the maximum seen in the left subtree into the right subtree traversal. Always passmax_valby value down the call stack.Updating running max too late: If you evaluate
node.val >= max_val, remember to updatenew_max = max(max_val, node.val)before passing to child recursions.Strictly greater vs greater-or-equal: A node is 'good' if its value is greater than OR EQUAL to the maximum on the path from root. Using strict
>drops valid nodes.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement calls a node good when nothing on the path from the root down to it is larger: whether a node counts depends only on the values above it, the Top-Down DFS signal.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
At each node: is_good = 1 if node.val >= max_so_far else 0, then both children get new_max = max(max_so_far, node.val), and the node returns is_good plus its children's counts.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: start
max_so_farat-inf(orroot.val), never at 0, since values can be negative.Compare with
>=, not>: a node equal to the path maximum is good. On[3,3,null,4,2]the second 3 counts and the answer is 3;>returns 2.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Top-Down DFS. Whether a node is good depends only on the values above it, so instead of looking back up the tree I carry the largest value seen so far down as an argument, max_so_far. At each node I compare: if its value is at least max_so_far, it's good. Then I pass the larger of the two to both children and add up the counts they return. Because the value travels as an argument, each call has its own copy, so the left subtree's changes never leak into the right one, and nothing needs undoing on the way back. The trap is the starting value: I start at minus infinity, not zero, because values can be negative and the root must always count. I also compare with greater-or-equal, since a tie with the path maximum is still good. Each node is visited once, so it's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Pre-order DFS passes down the maximum value seen along the path from root. If node.val >= max_so_far, increments good count and updates max_so_far. Each node visited once.
O(H) recursion stack
Call stack depth equals tree height H.
T(N) = O(N)
Derivation Progression
new_max = max(max_so_far, node.val)
Propagates maximum value down each branch in O(1) per frame.
is_good = 1 if node.val >= max_so_far else 0
Tests good node condition in constant time.
∑_{v} 1 = N ⟹ O(N)
Visits all N nodes once.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack depth
O(1) Scalar counter
O(1) Integer count
Boundary Best / Worst Cases
time, space.
time, space.
time, space.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "count good nodes", "no nodes with a value greater than X on path from root". Whether a node counts depends on the path above it: Top-Down DFS, passing max_so_far down each branch.
, values in . Time budget is linear time, space stack frames.
LeetCode allows nodes, so a chain is calls deep, far past CPython's default recursion limit of 1000: walk with an explicit stack of (node, max_so_far) pairs instead.