Log inSign up
mediumleetcodeNot Started

Count Good Nodes in Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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

Return the number of good nodes in the binary tree. Root is always considered a good node.

Example 1 · Example 1: Mixed Tree:

Input: root = [3, 1, 4, 3, null, 1, 5] Tree: 3 / \ 1 4 / / \ 3 1 5
Output: 4
Explanation: Good nodes are 3 (root), 3 (path 3->1->3: max is 3), 4 (path 3->4: max is 4), and 5 (path 3->4->5: max is 5).

Example 2 · Example 2: Strictly Decreasing:

Input: root = [3, 3, null, 4, 2] Tree: 3 / 3 / \ 4 2
Output: 3
Explanation: Nodes with value 3, 3, and 4 are good. Node 2 is not good because path max is 3.

Constraints:

  • The number of nodes in the binary tree is in the range [1, 105].
  • Each node's value is between [-104, 104].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Track ancestor state downwards in recursion without global interference.
  • Understand why passing max by value naturally isolates different branches.
  • Achieve single-pass O(n) runtime with O(h) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Condition depends on ancestor path from root to current node.
  • Monotonic path property / prefix maximum.
  • Counting valid nodes in a tree.

Algorithmic Decision Tree:

  • If node.val >= maxSoFar -> goodNodeCount++ and newMax = node.val.
  • Recurse left and right passing newMax.

Connected Patterns:

Binary Tree PathsPath SumLongest Univalue Path

1. Collect Path Elements for Each Node

Intuition

Store parent pointers or pass path array down to each node. For each node, linearly check if all ancestors are <= node.val.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Traverse tree maintaining list of ancestors path.
  2. Step 2: For each node, check if any value in path is strictly greater than node.val.
  3. Step 3: If no ancestor is greater, increment good node count.
  4. Step 4: Recurse on left and right children.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int count = 0;
10 void dfs(TreeNode* node, vector<int>& path) {
11 if (!node) return;
12 bool isGood = true;
13 for (int v : path) {
14 if (v > node->val) { isGood = false; break; }
15 }
16 if (isGood) count++;
17 path.push_back(node->val);
18 dfs(node->left, path);
19 dfs(node->right, path);
20 path.pop_back();
21 }
22 int goodNodes(TreeNode* root) {
23 vector<int> path;
24 dfs(root, path);
25 return count;
26 }
27};
28
29int main() {
30 // Sample driver execution
31 cout << "Execution completed successfully." << endl;
32 return 0;
33}
34

Time & Space Complexity

  • Time complexity: O(n * h) — Linearly checking path of length up to h for each of the n nodes.
  • Space complexity: O(h) — Ancestor path array and call stack take O(h) space.

2. BFS with Queue Storing (Node, MaxSoFar)

Intuition

Store pairs of (node, maxSoFar) in a BFS queue. For each popped pair, if node.val >= maxSoFar, increment answer and update maxSoFar before pushing children.

When to apply: Iterative alternative avoiding recursion stack limits.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Push pair (root, root.val) into queue.
  3. Step 3: Pop (node, maxVal). If node.val >= maxVal, goodCount++.
  4. Step 4: Push left and right children with max(maxVal, node.val).
  5. Step 5: Return goodCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int goodNodes(TreeNode* root) {
10 if (!root) return 0;
11 int count = 0;
12 queue<pair<TreeNode*, int>> q;
13 q.push({root, root->val});
14 while (!q.empty()) {
15 auto [node, maxSoFar] = q.front(); q.pop();
16 if (node->val >= maxSoFar) count++;
17 int nextMax = max(maxSoFar, node->val);
18 if (node->left) q.push({node->left, nextMax});
19 if (node->right) q.push({node->right, nextMax});
20 }
21 return count;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(w) — Queue holds maximum width w of tree.

3. Pure Recursive Preorder DFS (Single Integer State)

Intuition

At each node, test if node.val >= maxSoFar (good = 1, else 0). Update maxSoFar = max(maxSoFar, node.val) and return good + dfs(left, maxSoFar) + dfs(right, maxSoFar).

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Helper dfs(node, maxSoFar): if node == null return 0.
  2. Step 2: isGood = (node.val >= maxSoFar) ? 1 : 0.
  3. Step 3: newMax = max(maxSoFar, node.val).
  4. Step 4: Return isGood + dfs(node.left, newMax) + dfs(node.right, newMax).

Path Maximum DFS Trace for root = [3, 1, 4]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Inspect root 3
Visual state
Values and pointers at this exact step
tree
Root
3 (Good)
L
1
R
4

Node order shown; add connections to display explicit tree edges.

good: 3
Check / comparison
node.val (3) >= maxSoFar (3) -> Good!
Decision / next transition
Increment count to 1. Recurse to children with maxSoFar = 3.
Why this step matters

Step 1: Inspect root 3. Path max so far is 3. Since 3 >= 3, root 3 is a good node. Count = 1.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int dfs(TreeNode* node, int maxSoFar) {
9 if (!node) return 0;
10 int good = (node->val >= maxSoFar) ? 1 : 0;
11 int nextMax = max(maxSoFar, node->val);
12 return good + dfs(node->left, nextMax) + dfs(node->right, nextMax);
13 }
14public:
15 int goodNodes(TreeNode* root) {
16 return dfs(root, root->val);
17 }
18};
19
20int main() {
21 // Sample driver execution
22 cout << "Execution completed successfully." << endl;
23 return 0;
24}
25

Time & Space Complexity

  • Time complexity: O(n) — Processes each node in O(1) time.
  • Space complexity: O(h) — Call stack bounded by tree height h.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Path Linear SearchO(n * h)O(h)Reconstruct and scan entire ancestor array at each node.Redundant ancestor checks.
2.BFS Queue with (Node, MaxSoFar)O(n)O(w)Queue holds pairs of node and maximum value.Queue allocations.
3.Pure Recursive Preorder DFSOptimalO(n)O(h)Pass updated maxSoFar down recursion and return count sum.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: root is good, returns 1.
  • Monotonically decreasing tree (e.g. 5 -> 4 -> 3): only root is good, returns 1.
  • Monotonically increasing tree (e.g. 1 -> 2 -> 3): all nodes are good, returns n.
  • All nodes identical: all nodes are good, returns n.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that BFS with a queue storing (node, maxSoFar) is equally valid and avoids recursion limits.
  2. Note that node values can be negative, so initialize maxSoFar with root.val, NOT 0.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it sufficient to pass only the single maximum value maxSoFar instead of the complete list of all ancestors?

Back to DSA Sheet