343. Count Good Nodes in Binary Tree

A node is good exactly when its value is at least the maximum value seen on the path from the root. Carry that running maximum down the recursion.

The invariant

Walk down from the root carrying mx = the largest value seen so far on the current root-to-node path. A node is good iff node.val >= mx. Before recursing into children, update mx = max(mx, node.val).

Walk-through

dfs(node, mx):
    if node is None: return 0
    good = 1 if node.val >= mx else 0
    mx = max(mx, node.val)
    return good + dfs(node.left, mx) + dfs(node.right, mx)
return dfs(root, -inf)

The root is always good (nothing precedes it).

Worked example

[3,1,4,3,null,1,5]:

• 3 (root) good (mx→3).
• left 1: 1 ≥ 3? no. Its child 3: 3 ≥ 3? yes (mx→3).
• right 4: 4 ≥ 3? yes (mx→4). Child 1: no. Child 5: 5 ≥ 4? yes.
• Good nodes: 3, 3, 4, 5 → 4.

Complexity

• Time: O(n) — one visit per node.
• Space: O(h) recursion depth.

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }

    private int dfs(TreeNode node, int mx) {
        if (node == null) return 0;
        int good = node.val >= mx ? 1 : 0;
        int nextMax = Math.max(mx, node.val);
        return good + dfs(node.left, nextMax) + dfs(node.right, nextMax);
    }
}