1448. Count Good Nodes in Binary Tree

Medium · solved 2026-10-05 · Open on LeetCode

treebinary-treedfs

Time O(n) · Space O(h)

How to get there

Carry the path's maximum down

1. Restate what makes a node good. No node on the path from the root down to it holds a larger value. Equivalently, its value is at least the largest value above it.

2. Count LeetCode’s first example by hand and find where it gets slow. In [3, 1, 4, 3, null, 1, 5], the good nodes are the root 3, the 4 under it, the 3 on the path 3 → 1 → 3, and the 5 on 3 → 4 → 5: four in all. The two 1s are not. Checking each node against its whole path works, but it re-reads the path for every node: O(h) work per node.

3. Find what to remember. Not the whole path, just its largest value. A child’s path is its parent’s path plus the child itself, so the child’s maximum is max(parent's maximum, child's value): one number, handed down from parent to child.

4. Let any depth-first walk carry it. Push each node together with its path’s maximum, as (node, best) pairs on a stack, the same way 104 carries (node, depth). Each node only needs its own path, so the order of the walk doesn’t matter.

5. Read the test against what best holds. In solution.py, a child is pushed with max(best, child.val), so best includes the node itself and is never below current.val. The test current.val >= best therefore holds exactly when the node is its path’s largest value, ties included. Pushing children with max(best, current.val) and starting the root at negative infinity carries the ancestors’ maximum only, so that the test reads exactly like the definition.

6. Check the cost. Each node is pushed and popped once: O(n) time, and O(h) space for the stack.

The reusable recipe: when a node’s answer depends on its ancestors, pass a summary of the path down with each node, such as a running maximum, instead of the path itself.

Let the pair's meaning write each line

Variable	Always means
`(current, best)` on the stack	`best` is the largest value on the path from the root down to `current`, `current` included
`solution`	how many of the nodes popped so far are good

Code	What happened	What it keeps true
`stack, solution = [(root, root.val)], 0`	the path to the root is the root alone	its largest value is its own
`current, best = stack.pop()`	the next node and its path’s maximum come off
`stack.append((child, max(best, child.val)))`	a child’s path is this path plus the child	its maximum is the larger of the two
`if current.val >= best: solution += 1`	`best` already includes `current`, so this is `current.val == best`	the node is good exactly when nothing on its path is larger
`return solution`	the stack is empty	every node has been checked

The test needs >=, not >: a node equal to the largest value above it is still good, like the 3 under 3 → 1 in LeetCode’s first example.

The method carries over: put next to each node on the stack exactly what its check needs, and derive the child’s value from the parent’s.

Alternatives compared

Approach	Time	Space	How it works
Check each node against its whole path	O(n · h)	O(h)	Keep the path on a list and compare each node with every value on it.
Recursion passing the maximum down	O(n)	O(h)	`visit(node, best)` counts the node if `node.val >= best`, then visits both children with `max(best, node.val)`.
Stack of (node, path maximum) (chosen, `solution.py`)	O(n)	O(h)	Push each child with its path’s maximum; a popped node is good when it equals that maximum.
Queue of (node, path maximum)	O(n)	O(w)	The same pairs taken level by level with breadth-first search; w is the widest level.

Every approach that carries the maximum does the same O(1) check per node; they differ only in what holds the pairs. A tree can have 100,000 nodes, so a chain that deep exceeds Python’s default limit of 1,000 recursive calls, while the stack has no such limit: solution.py ran a 100,000-node chain when run locally.

solution.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        if not root:
            return 0

        stack, solution = [(root, root.val)], 0

        while stack:
            current, best = stack.pop()
            if current.right:
                stack.append((current.right, max(best, current.right.val)))
            if current.left:
                stack.append((current.left, max(best, current.left.val)))
            if current.val >= best:
                solution += 1

        return solution

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.