How do you solve Count Good Nodes in Binary Tree?

Use a DFS helper function that takes the current node and the maximum value seen so far on the path. At each node, determine if it is good by comparing its value to the max. Update the max if the current node's value is higher, then recursively count good nodes in the left and right subtrees. Sum these counts and return the total. This approach visits each node once, resulting in O(n) time complexity.

What pattern does Count Good Nodes in Binary Tree use?

The Pattern: DFS (Stateful Exploration) The Heuristic: When a problem requires evaluating nodes based on the path from the root, carry forward relevant state information (like max value) during DFS recursion to enable constant-time checks at each node.

Count Good Nodes in Binary Tree — DFS

Q: What is the time complexity of Count Good Nodes in Binary Tree?

O(n). Each node is visited exactly once during the DFS traversal, and all operations at each node are O(1).

Problem

Given the root of a binary tree, return the number of good nodes in the tree. A node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

The number of nodes in the binary tree is in the range [1, 10⁵]
−10⁴ ≤ Node.val ≤ 10⁴

Example

Input: root = [3,1,4,3,null,1,5]

Output: 4

Starting at the root (3), it is good because no nodes are greater on the path. The left child (1) is not good because 3 > 1 on the path. The right child (4) is good because 4 >= 3. The left child of 1 (3) is good because 3 >= 3. The right child of 4 (5) is good because 5 >= 4. The right child of 4 (1) is not good because 4 > 1. Total good nodes are 4.

Approach

Straightforward Solution

A brute-force approach would check for each node all ancestors to verify if any have a greater value, resulting in O(n^2) time in the worst case, which is inefficient for large trees.

Core Observation

A node is good if its value is at least as large as every value on the path from the root to that node. This means the problem requires tracking the maximum value seen so far on the path to each node.

Path to Optimal

Preview

The key insight is to carry forward the maximum value encountered on the path as the recursion descends the tree. This allows each node to be evaluated in O(1) time by comparing its value to the current maximum…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a DFS helper function that takes the current node and the maximum value seen so far on the path. At each node, determine if it is good by comparing its value to the max…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited exactly once during the DFS traversal, and all operations at each node are O(1).

Space

O(h)

The recursion stack depth is proportional to the height h of the tree. In the worst case of a skewed tree, this can be O(n), but for balanced trees it is O(log n). No additional data structures proportional to n are used.

Solution

Python

1class Solution:
  def goodNodes(self, root: TreeNode) -> int:
      
      def dfs(node, max_val):
          if not node:
              return 0
          
          res = 1 if node.val >= max_val else 0
          max_val = max(max_val, node.val)
          res += dfs(node.left, max_val)
          res += dfs(node.right, max_val)
          return res
      
      return dfs(root, root.val)

Step-by-Step Solution

1

Evaluate Node Goodness and Propagate Maximum Value via DFS

4def dfs(node, max_val):
  if not node:
      return 0
  res = 1 if node.val >= max_val else 0
  max_val = max(max_val, node.val)
  res += dfs(node.left, max_val)
  res += dfs(node.right, max_val)
  return res

Objective

To recursively count good nodes by comparing each node's value to the maximum value seen on the path and updating this maximum as the recursion proceeds.

Key Insight

Carrying the maximum value seen so far during DFS enables immediate evaluation of whether the current node is good. This eliminates the need for ancestor traversal or additional data structures. The recursion naturally explores all nodes, accumulating counts efficiently.

Interview Quick-Check

Core Logic

The DFS function uses the current max value to decide if the node is good, then updates the max and recursively counts good nodes in left and right subtrees, summing results.

State & Boundaries

The base case returns 0 for null nodes, ensuring the recursion terminates correctly.

Common Pitfalls & Bugs

Forgetting to update the max value before recursive calls can cause incorrect counts, as subsequent nodes might be evaluated against stale max values.

Complexity

This approach guarantees O(n) time and O(h) space, where h is the tree height, by visiting each node once and maintaining only path state.

2

Initiate DFS Traversal from Root with Initial Maximum

To start the DFS recursion from the root node, initializing the maximum value with the root's value.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 8 Critical

res = 1 if node.val >= max_val else 0

Determine if the current node is good by comparing its value to the max value on the path.

This conditional check is the core decision point that identifies good nodes, enabling counting only those nodes that meet the problem's criteria.

Line 9 Critical

max_val = max(max_val, node.val)

Update the max value to the maximum of the current max and the current node's value.

Updating the max value ensures that the path state accurately reflects the highest value seen so far, which is critical for correct evaluation of descendant nodes.

Line 12 Critical

return res

Return the total count of good nodes from the current node and its subtrees.

Summing the current node's goodness with counts from left and right subtrees aggregates the total good nodes in the entire subtree rooted at this node.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why is it necessary to pass the maximum value seen so far down the recursion rather than recomputing it at each node?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Count Good Nodes in Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Count Good Nodes in Binary Tree drill

or drill a free problem

1	`class Solution:`
2	`def goodNodes(self, root: TreeNode) -> int:`
3
4	`def dfs(node, max_val):`
5	`if not node:`
6	`return 0`
7
8	`res = 1 if node.val >= max_val else 0`
9	`max_val = max(max_val, node.val)`
10	`res += dfs(node.left, max_val)`
11	`res += dfs(node.right, max_val)`
12	`return res`
13
14	`return dfs(root, root.val)`

4	`def dfs(node, max_val):`
5	`if not node:`
6	`return 0`
8	`res = 1 if node.val >= max_val else 0`
9	`max_val = max(max_val, node.val)`
10	`res += dfs(node.left, max_val)`
11	`res += dfs(node.right, max_val)`
12	`return res`