Count Good Nodes: what the path maximum tells you as you descend

The definition of a good node is deceptively clean: no ancestor on the path from root to that node has a strictly greater value. Root always qualifies — it has no ancestors at all. The catch is in the word "path." If you take the definition literally, you end up dragging the whole history of the path down the tree with you, checking it at every node. That is the brute-force approach, and it is slow for a reason that the constraints make obvious.

The tree above is Example 1: root = [3,1,4,3,null,1,5]. Four nodes are good: the root (3), the right child (4), the right-right child (5), and the left-left child (3). Everything the optimal solution does flows from recognizing that you only need the single largest value seen so far, not the entire list of ancestors.

The problem

Given a binary tree, count how many nodes are "good" — a node X is good if no node on the path from root to X has a value strictly greater than X's own value. The root always qualifies. Full statement: LeetCode 1448.

Constraints:
- The number of nodes in the binary tree is in the range [1, 10^5].
- Each node's value is between [-10^4, 10^4].

What the constraints force

Node count is in [1, 10^5]. That alone rules out O(n²). A path-scan that checks each ancestor against the current node visits, on average, O(depth) ancestors per node. For a balanced tree depth is O(log n), giving you O(n log n). For a right-skewed chain of 10^5 nodes the depth hits O(n), making the full solution O(n²) — around 10^10 operations. You would time out by several orders of magnitude.

Node values are in [-10^4, 10^4]. Two things fall out of this. First, you need your initial "max seen so far" to be smaller than any value in the tree — float('-inf') in Python or int.MinValue in C# work and survive the negative value regime. If you initialized to 0, a tree like [-1, -2, -3] would misclassify every node. Second, you cannot treat 0 as a sentinel for anything structural.

The range is tight enough that you do not need to worry about integer overflow when storing the running maximum — int.MinValue on the initial call is the only boundary that matters, and values are bounded at 10^4.

Approach 1: carrying the full path (brute force)

The most literal reading of the problem: maintain a list of all values on the current root-to-node path. To test a node, scan the list for any value greater than the current node's value. Backtrack (pop the path) when you leave a 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:
        def dfs(node, path):
            if not node:
                return 0
 
            path.append(node.val)
 
            is_good = True
            for val in path[:-1]:  # exclude the node itself
                if val > node.val:
                    is_good = False
                    break
 
            count = 1 if is_good else 0
            count += dfs(node.left, path)
            count += dfs(node.right, path)
 
            path.pop()  # backtrack
            return count
 
        return dfs(root, [])

public class Solution {
    public int GoodNodes(TreeNode root) {
        return DFS(root, new List<int>());
    }
 
    private int DFS(TreeNode node, List<int> path) {
        if (node == null) return 0;
 
        path.Add(node.val);
 
        bool isGood = true;
        for (int i = 0; i < path.Count - 1; i++) {
            if (path[i] > node.val) {
                isGood = false;
                break;
            }
        }
 
        int count = isGood ? 1 : 0;
        count += DFS(node.left, path);
        count += DFS(node.right, path);
 
        path.RemoveAt(path.Count - 1);  // backtrack
        return count;
    }
}

At each node you scan up to O(depth) previous values. Across all nodes, total work is O(n * depth) — O(n log n) average on a balanced tree, O(n²) worst case on a skewed chain. Space is O(h) for both the call stack and the path list, where h is tree height. This is the approach you almost never want to ship for n = 10^5.

The insight that collapses path-scanning to O(1) per node

The scan is redundant. When you reach a node, you do not need to re-examine every ancestor. You only care about the maximum among them. And crucially, you already have that maximum — you computed it on the way down from the root. Instead of keeping the full list and scanning it, keep one number: the maximum value seen on the path from root to the current node's parent.

A node is good if and only if node.val >= max_so_far. After checking, update max_so_far = max(max_so_far, node.val) before going deeper. The updated value becomes the constraint for every node in the subtree below. This is top-down parameter passing: you push state from parent to children instead of reading it back from a stored structure.

Approach 2: DFS with a running maximum

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

public class Solution {
    public int GoodNodes(TreeNode root) {
        return DFS(root, int.MinValue);
    }
 
    private int DFS(TreeNode node, int maxSoFar) {
        if (node == null) return 0;
 
        int count = node.val >= maxSoFar ? 1 : 0;
        int newMax = Math.Max(maxSoFar, node.val);
 
        count += DFS(node.left, newMax);
        count += DFS(node.right, newMax);
        return count;
    }
}

Every node is visited exactly once. At each node, the work is O(1): one comparison, one max call, two recursive calls. Time is O(n). Space is O(h) for the call stack — O(log n) on a balanced tree, O(n) on a skewed chain. No auxiliary data structure beyond the call frames themselves.

Hand trace through Example 1: root = [3,1,4,3,null,1,5]

Starting call: dfs(node=3, max_so_far=-inf)

Step 1: node=3,  max_so_far=-inf  ->  3 >= -inf, count=1,  new_max=3
  Step 2: node=1,  max_so_far=3    ->  1 < 3,     count=0,  new_max=3
    Step 3: node=3,  max_so_far=3  ->  3 >= 3,    count=1,  new_max=3
              node.left=null -> 0
              node.right=null -> 0
              returns 1
    node.right=null -> 0
    returns 0 + 1 + 0 = 1
  Step 4: node=4,  max_so_far=3    ->  4 >= 3,    count=1,  new_max=4
    Step 5: node=1,  max_so_far=4  ->  1 < 4,     count=0,  new_max=4
              node.left=null -> 0, node.right=null -> 0
              returns 0
    Step 6: node=5,  max_so_far=4  ->  5 >= 4,    count=1,  new_max=5
              node.left=null -> 0, node.right=null -> 0
              returns 1
    returns 1 + 0 + 1 = 2
  returns 1 + 2 = 3
returns 1 + 1 + 3 = 4

Four good nodes. The trace also shows why node 1 (left child of root) is not good — by the time you reach it, the path maximum is already 3, which beats its value.

Why >= and not >

The condition is node.val >= max_so_far, not strictly greater than. The problem says a good node is one where no ancestor has a value strictly greater than its own. Equality is allowed — a node whose value ties the maximum is still good. Getting this wrong (> instead of >=) causes exactly one class of failure: nodes that equal the current path maximum get miscounted as bad.

Edge cases worth naming

Single node (root = [1]): DFS calls dfs(node=1, max_so_far=-inf). The condition 1 >= -inf is true. Both children are null and return 0. Result is 1. Correct — root is always good.

All values identical (e.g., [5,5,5,5,5]): every node has node.val == max_so_far from the second level onward. All are good. The >= in the condition handles this correctly; > would count only the root.

Strictly decreasing top-down (e.g., [5,4,3]): only the root is good. Each child sees a max_so_far equal to its parent's value, which is larger than the child. The result is 1 regardless of tree size.

All negative values (e.g., [-3,-4,-1]): if you initialize max_so_far to 0 rather than -inf, the root (value -3) would fail the check (-3 >= 0) and the entire tree would return 0 good nodes — wrong. Starting at float('-inf') or int.MinValue ensures the root always passes, as the problem guarantees.

Right-skewed chain of 10^5 nodes with all values equal: every node is good. With Approach 1, this is the worst case for both time (O(n²) path scans) and space (O(n) path list and call stack together). With Approach 2, you pay O(n) time and O(n) call stack — still the worst case for space on a skewed tree, but inherently unavoidable since you must visit every node.

Approach comparison

The space difference is smaller than the time difference — both approaches use O(h) for the call stack, and Approach 1 adds another O(h) for the path list. On a balanced tree that extra factor is O(log n), which is negligible. The real cost is in time: O(n²) vs O(n) at n = 10^5 is the difference between shipping and timing out.

What I would write in an interview or production context

Approach 2 immediately. Not because Approach 1 is wrong, but because the insight is too clean to skip: you do not need the full path, you need the scalar summary of the path. Once you see that, the rest follows in four lines. Approach 1 is worth mentioning as the direct-translation starting point, specifically to motivate the optimization — but I would not code it in full; I would say "carrying the path is O(n²), and all we actually need is the running maximum" and go straight to Approach 2.

The pattern here is top-down parameter passing: instead of reading an accumulator from a stored structure, you push state as a parameter from parent to child. It sidesteps the need for any external data structure and keeps the function self-contained. This exact mechanism appears in dozens of tree problems.

Where this sits in the trees series, and what comes next

This is problem 12 in the series. By this point you have seen DFS on a single tree (maximum depth, invert, same tree), BFS level-order traversal, BST validation, and subtree matching. Count Good Nodes is the first problem in the series that requires you to carry information strictly downward — from ancestors to descendants — rather than accumulating results from leaves upward (as in max depth) or passing no extra state at all (as in invert).

The underlying pattern is "path information propagated top-down via DFS parameters." It appears in:

Path Sum (112): is there any root-to-leaf path whose values sum to a target? Same structure — carry the current running sum as a parameter, check at leaves. The difference is you are summing instead of maximizing, and the check is at leaf nodes only.

Path Sum II (113): collect all such paths. Adds backtracking to the path list — which brings you back to something like Approach 1's mechanics, but now the path list is the output, not an intermediate you can optimize away.

Binary Tree Maximum Path Sum (124): the hardest escalation. A "path" no longer has to start at root, so the top-down parameter trick does not directly apply. You need a bottom-up DFS that returns the best single-branch gain from each node and tracks a global maximum across all root-spanning paths.

Longest Univalue Path (687): carry a different invariant — the length of the current univalue chain ending at the parent. Shows that top-down parameter passing works with any scalar invariant, not just max/sum.

The mental model to carry forward: whenever a tree problem asks you to check a condition that depends on the path from root to the current node, think "what is the minimal scalar (or small struct) I can pass from parent to child that captures everything relevant about that path?" For this problem, the answer is the single maximum seen so far. Getting comfortable with that reductive step is what makes an otherwise O(n²) problem obvious to solve in O(n).