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

Examples

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Good nodes: 3 (root), 3 (left-left), 4, 5.
Node 1 is not good because 3 > 1 on its path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Good nodes: 3 (root), 3, 4.

Example 3:

Input: root = [1]
Output: 1

Constraints

  • Number of nodes in the tree is in the range [1, 10^5]
  • -10^4 <= Node.val <= 10^4

Thinking Process

A node is “good” if node->val >= max value on the path from root to this node. So we need to carry the running maximum as we traverse downward.

This is a classic top-down DFS with state pattern: pass extra information (the path maximum) from parent to child.

Algorithm

  1. Start DFS from root with maxVal = INT_MIN (or root->val)
  2. At each node: if node->val >= maxVal, it’s good – increment count
  3. Update maxVal = max(maxVal, node->val) and recurse on children
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

class Solution {
public:
    int goodNodes(TreeNode* root) {
        cnt = 0;
        dfs(root, INT_MIN);
        return cnt;
    }

private:
    int cnt;
    void dfs(TreeNode* node, int maxVal) {
        if (!node) return;
        if (node->val >= maxVal) {
            cnt++;
            maxVal = node->val;
        }
        dfs(node->left, maxVal);
        dfs(node->right, maxVal);
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: A node is “good” if node->val >= max value on the path from root to this node. So we need to carry the running maximum as we traverse downward.

How the code works:

  1. Start DFS from root with maxVal = INT_MIN (or root->val)
  2. At each node: if node->val >= maxVal, it’s good – increment count
  3. Update maxVal = max(maxVal, node->val) and recurse on children

Walkthrough — input root = [3,1,4,3,null,1,5], expected output 4:

Good nodes: 3 (root), 3 (left-left), 4, 5. Node 1 is not good because 3 > 1 on its path.

Comparison

Approach Time Space Notes
Recursive DFS O(n) O(h) Cleanest, natural top-down
Iterative DFS O(n) O(h) Avoids stack overflow
BFS O(n) O(w) Level-order, wider space for balanced trees

Common Mistakes

  • Forgetting that the root is always good (initializing maxVal too high)
  • Not updating maxVal when the current node is good
  • Using > instead of >= (a node equal to the path max is still good)

Key Takeaways

  • “Check property along root-to-node path” = top-down DFS carrying state
  • The pattern of passing a running aggregate (max, sum, etc.) downward appears in many tree problems
  • All three traversal styles (recursive DFS, iterative DFS, BFS) work here since we only need to visit every node once with its path context

References

Template Reference