← DSA Atlas
Dedicated problem page · #1448

Count Good Nodes in Binary Tree

MediumTrees and Binary Search TreesRoot-to-node max propagationDFS carrying the running maximum along the path
Solve on LeetCode ↗
1448
MediumTrees and Binary Search TreesDFS carrying the running maximum along the pathRoot-to-node max propagation

Count Good Nodes in Binary Tree

Given the root of a binary tree, a node X is called good if on the path from the root down to X there is no node with a value greater than X. (The root is always good.) Return the total number of good nodes in the tree.

Open official problem prompt ↗
In plain English

Count how many nodes are at least as large as every ancestor on their root-to-node path.

Picture it like this

Hike a trail that only branches downward from a summit. You are 'good' at a spot if you can see over every point behind you — no earlier point on your path was taller than where you stand.

Example
Input
root = [3,1,4,3,null,1,5]
Output
4
Why
Good nodes are root 3, the right child 4, its right child 5, and the 3 that is the left child of node 1 (path max 3, and 3 >= 3).
Constraints
The number of nodes in the tree is in the range [1, 10^5]-10^4 <= Node.val <= 10^4
Pattern lesson

See the pattern, then code

Root-to-node max propagation
Recognition clue

The 'good' condition depends only on the maximum value seen on the path from the root — a classic signal to DFS while threading a running maximum down the recursion.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. A node is good exactly when its value is at least the maximum of all ancestors. So carry that path maximum downward: compare, count, then update the maximum before descending.

New words, made simpleKnow these before the algorithm
Good node
A node whose value is >= the maximum value among all nodes from the root down to it (inclusive of nothing above it that is larger).
Path maximum
The largest value encountered on the current root-to-node path; the single piece of state DFS threads downward.
Preorder DFS
Process a node (compare and count) before recursing into its children, so the updated max reaches them.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
For each node, re-walk to the root

Redundantly re-scans ancestors; wasteful and needs parent links or a path stack.

For every node, traverse back up to the root and check whether any ancestor is larger.

Time O(n * h)Space O(h)
Best choiceDFS threading the path maximum

Single traversal, each node visited once with O(1) work.

Pass the running max down; a node is good iff its value >= that max, then update and recurse.

Time O(n)Space O(h)
The rule we keep true

Invariant

When DFS enters a node, path_max equals the maximum value among all strict ancestors of that node (and the initial call seeds it with the root's own value so the root counts as good).

Why this is correct

Reasoning

Goodness of a node depends only on the ancestor maximum, which is order-independent — so knowing that single number when we arrive at the node is sufficient to decide correctly. Because we update the max before descending, every child receives the true maximum of its full ancestor path, and each node is decided exactly once.

The algorithm in three movesSay these aloud before coding
1DFS from the root, passing down the max value seen so far (start at the root's own value or -infinity)

visit 3: max=3, good (count 1)

2At each node, count it as good if its value is >= the incoming max

visit 4: max=3, 4>=3 good (count 3 incl. subtree 3)

3Update the max to max(incoming, node.val)

visit 5: max=4, 5>=4 good -> total 4

4Sum the good counts from both subtrees plus the current node

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
11
42
33
14
55
1 · Readnode 3, path_max=3
2 · Ask3 >= 3?
3 · Update stategood=1, new max=3
4 · ResultRecurse into left(1) and right(4)
Key takeaway

Highlighted nodes (3, 4, 5, and the deep 3) are good; each is at least the maximum on its root path.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 13-15Base case

    A null child contributes zero good nodes.

  2. 2
    Lines 16-17Decide and update

    Count the node if it meets or exceeds the ancestor max, then fold its own value into the max for descendants.

  3. 3
    Lines 18-20Accumulate subtrees

    Sum good counts from left and right using the updated max.

  4. 4
    Lines 21Seed the recursion

    Starting path_max at root.val guarantees the root is counted, since root.val >= root.val.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single node: answer is 1 (root is always good)
  • All equal values: every node is good because >= uses non-strict comparison
  • Strictly increasing downward chain: every node is good
  • Negative values: seeding with root.val (not 0) is essential so negatives near the root are handled correctly
!

Common beginner mistakes

  • Using strict > instead of >=, which would wrongly exclude nodes equal to the ancestor max
  • Seeding path_max with 0 or a fixed constant instead of the root's value or -infinity, breaking on negative values
  • Updating the max after recursing instead of before, so children see a stale maximum
  • Forgetting to include the current node's contribution when summing subtree results
Check your understanding

Why must the comparison be >= rather than >?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split