Problem Statement

Count Good Nodes in Binary Tree

A binary tree is a set of nodes where each node holds a value and can point to up to two children, a left one and a right one. The very top node is called the root. Picture a family tree that branches downward. Now walk from the root down to some node X, following the links. We call X a good node if, on that whole walk down, you never passed a value bigger than X's own value. In other words, X is at least as big as everything above it on its path. Your job is to count how many good nodes the tree has.

mediumTreeTreesTime: O(n) · Space: O(h)

Signals to notice

count nodes not smaller than all ancestors abovetrack maximum along pathDFS with running state

Brute force first

For each node, check all ancestors. Re-traverses the path to root for every node. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

DFS passing the maximum value seen so far from root to current node. If current node ≥ maxSoFar, it's a 'good' node. Update maxSoFar for children. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `root=[3,1,4,3,null,1,5] (root 3 -> left 1{left:3}, right 4{left:1,right:5})`

dfs(3, -inf): 3>=-inf -> good, newMax=3, count=1
dfs(1, 3): 1<3 -> not good, newMax=3 (recurse into left subtree)
  dfs(3, 3): 3>=3 -> good, newMax=3, count=2
dfs(4, 3): 4>=3 -> good, newMax=4, count=3 (recurse into right subtree)
  dfs(1, 4): 1<4 -> not good
  dfs(5, 4): 5>=4 -> good, newMax=5, count=4
All branches hit null -> return 0; sums bubble up
return 4

What must stay true

maxSoFar always holds the largest value on the path from root to the current node. A node is 'good' if and only if its value ≥ maxSoFar. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

function dfs(node, maxSoFar):
    if node is null: return 0
    good = 1 if node.val >= maxSoFar else 0
    newMax = max(maxSoFar, node.val)
    return good + dfs(node.left, newMax) + dfs(node.right, newMax)
return dfs(root, -infinity)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Updating maxSoFar globally instead of per-path — each path from root has its own running maximum. Pass it as a parameter, don't store it as shared state. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Trees Pattern