146. Count Good Nodes in Binary Tree
🔗 LeetCode Problem: 1448. Count Good Nodes in Binary Tree
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, DFS, Recursion, Path Tracking
Problem Statement
Given a binary tree root, 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.
Return the number of good nodes in the binary tree.
Example 1:
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
Example 2:
Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
Example 3:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
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]
🌳 Visual Understanding - What is a "Good" Node?
Definition:
A node X is "GOOD" if:
In the path from root to X,
NO node has value > X
In other words:
X >= all nodes on path from root to X
OR
X is the MAXIMUM (or tied for maximum) on its path!
Example 1 - Visual Breakdown:
Tree:
3
/ \
1 4
/ / \
3 1 5
Path analysis:
Node 3 (root):
Path: [3]
Max on path: 3
3 >= 3? YES → GOOD ✓
Node 1 (left child):
Path: [3, 1]
Max on path: 3
1 >= 3? NO → NOT GOOD ✗
Node 4 (right child):
Path: [3, 4]
Max on path: 4
4 >= 4? YES → GOOD ✓
Node 3 (left-left):
Path: [3, 1, 3]
Max on path: 3
3 >= 3? YES → GOOD ✓
Node 1 (right-left):
Path: [3, 4, 1]
Max on path: 4
1 >= 4? NO → NOT GOOD ✗
Node 5 (right-right):
Path: [3, 4, 5]
Max on path: 5
5 >= 5? YES → GOOD ✓
Total GOOD nodes: 4 (nodes 3, 4, 3, 5)
Visual with Color Coding:
Tree with GOOD nodes marked:
3 ✓ (root, always good)
/ \
1 ✗ 4 ✓ (4 >= 3)
/ / \
3✓ 1✗ 5✓
(3>=3) (1<4) (5>=4)
Count: 4 GOOD nodes
Example 2 - Tricky Case:
Tree:
3
/
3
/ \
4 2
Node 3 (root):
Path: [3]
3 >= 3? YES → GOOD ✓
Node 3 (left):
Path: [3, 3]
Max: 3
3 >= 3? YES → GOOD ✓
Node 4 (left-left):
Path: [3, 3, 4]
Max: 4
4 >= 4? YES → GOOD ✓
Node 2 (left-right):
Path: [3, 3, 2]
Max: 3
2 >= 3? NO → NOT GOOD ✗
Total: 3 GOOD nodes
Key Insight:
To check if node is GOOD:
Compare node.val with MAX seen on path so far
If node.val >= pathMax:
Node is GOOD!
Update pathMax for children
Else:
Node is NOT GOOD
Keep pathMax same for children
We need to TRACK the maximum as we go down! 🎯
🧠 The AHA Moment - Track Path Maximum!
The Core Idea:
As we traverse the tree:
- Keep track of MAXIMUM value seen on path
- At each node, compare with this maximum
- If current >= max: GOOD!
- Update max for recursive calls to children
This is PERFECT for DFS with parameter passing! ✓
Why DFS Works Perfectly:
DFS naturally follows paths from root to leaves
At each node:
1. Check: node.val >= pathMax?
2. Count if good
3. Recurse with UPDATED pathMax
Path maximum propagates down naturally! 🎯
Visual Algorithm:
dfs(node, pathMax):
Is node good?
good = (node.val >= pathMax) ? 1 : 0
Update pathMax for children:
newMax = max(pathMax, node.val)
Count in subtrees:
leftCount = dfs(node.left, newMax)
rightCount = dfs(node.right, newMax)
Return total:
return good + leftCount + rightCount
🧠 Recursive Thinking - Building the Solution
Base Case:
What's the simplest case?
→ null node
What to return?
→ 0 (no nodes, so 0 good nodes)
if (node == null) return 0;
Recursive Case:
For any non-null node:
STEP 1: Check if current node is good
isGood = (node.val >= pathMax)
count = isGood ? 1 : 0
STEP 2: Update pathMax for children
newMax = max(pathMax, node.val)
Why? Children need to compare with
the maximum INCLUDING current node!
STEP 3: Recurse on children
leftGood = dfs(node.left, newMax)
rightGood = dfs(node.right, newMax)
STEP 4: Return total count
return count + leftGood + rightGood
What Each Node Returns:
Each node returns:
Number of GOOD nodes in its subtree (including itself)
Example:
3 (returns 4)
/ \
1 4 (returns 2)
/ / \
3 1 5
Node 5: returns 1 (itself is good)
Node 1: returns 0 (itself not good)
Node 4: returns 1 + 0 + 1 = 2
Node 3 (left-left): returns 1
Node 1 (left): returns 0 + 1 = 1
Node 3 (root): returns 1 + 1 + 2 = 4 ✓
🎯 Solution: DFS with Path Maximum
Implementation:
class Solution {
public int goodNodes(TreeNode root) {
// Start with root value as initial maximum
// WHY? Root is always on path, and is the first node
return dfs(root, root.val);
}
private int dfs(TreeNode node, int pathMax) {
// Base Case: null node contributes 0 good nodes
if (node == null) {
return 0;
}
// STEP 1: Check if current node is good
// Good = no node on path has value > current
// Equivalent: current >= max on path
int count = 0;
if (node.val >= pathMax) {
count = 1; // This node is good!
}
// STEP 2: Update pathMax for children
// WHY? Children must consider current node in their path
// The new maximum is either:
// - Current pathMax (if current node is smaller)
// - Current node value (if it's larger)
int newMax = Math.max(pathMax, node.val);
// STEP 3: Count good nodes in left subtree
// Pass newMax so left children know the maximum on their path
int leftGood = dfs(node.left, newMax);
// STEP 4: Count good nodes in right subtree
// Pass newMax so right children know the maximum on their path
int rightGood = dfs(node.right, newMax);
// STEP 5: Return total good nodes in this subtree
// Current node (if good) + left subtree + right subtree
return count + leftGood + rightGood;
}
}
Why Root Value as Initial Max?
Root is ALWAYS good!
Why?
Path to root: [root]
Maximum on path: root.val
root.val >= root.val? YES ✓
So we start with root.val as initial pathMax
Alternative: Start with Integer.MIN_VALUE
Would also work (root.val >= MIN_VALUE always true)
But root.val is more semantic
🔍 Detailed Dry Run - Complete Recursion
Tree:
3
/ \
1 4
/ / \
3 1 5
Complete Call Stack Visualization:
═══════════════════════════════════════════════════
CALL STACK - SHOWING EVERY STEP
═══════════════════════════════════════════════════
Level 0: dfs(3, 3)
│
├─ node = 3, pathMax = 3
├─ Is good? 3 >= 3? YES → count = 1 ✓
├─ newMax = max(3, 3) = 3
│
├─ LEFT: dfs(1, 3) ────────────────────────────────┐
│ │
│ Level 1: dfs(1, 3) │
│ │ │
│ ├─ node = 1, pathMax = 3 │
│ ├─ Is good? 1 >= 3? NO → count = 0 ✗ │
│ ├─ newMax = max(3, 1) = 3 │
│ │ │
│ ├─ LEFT: dfs(3, 3) ───────────────────────┐ │
│ │ │ │
│ │ Level 2: dfs(3, 3) │ │
│ │ │ │ │
│ │ ├─ node = 3, pathMax = 3 │ │
│ │ ├─ Is good? 3 >= 3? YES → count = 1 ✓ │ │
│ │ ├─ newMax = max(3, 3) = 3 │ │
│ │ │ │ │
│ │ ├─ LEFT: dfs(null, 3) → return 0 │ │
│ │ ├─ RIGHT: dfs(null, 3) → return 0 │ │
│ │ │ │ │
│ │ └─ return 1 + 0 + 0 = 1 │ │
│ │ │ │
│ ├─ RIGHT: dfs(null, 3) → return 0 │ │
│ │ │ │
│ └─ return 0 + 1 + 0 = 1 │ │
│ │
├─ RIGHT: dfs(4, 3) ───────────────────────────────┐
│ │
│ Level 1: dfs(4, 3) │
│ │ │
│ ├─ node = 4, pathMax = 3 │
│ ├─ Is good? 4 >= 3? YES → count = 1 ✓ │
│ ├─ newMax = max(3, 4) = 4 │
│ │ │
│ ├─ LEFT: dfs(1, 4) ───────────────────────┐ │
│ │ │ │
│ │ Level 2: dfs(1, 4) │ │
│ │ │ │ │
│ │ ├─ node = 1, pathMax = 4 │ │
│ │ ├─ Is good? 1 >= 4? NO → count = 0 ✗ │ │
│ │ ├─ newMax = max(4, 1) = 4 │ │
│ │ │ │ │
│ │ ├─ LEFT: dfs(null, 4) → return 0 │ │
│ │ ├─ RIGHT: dfs(null, 4) → return 0 │ │
│ │ │ │ │
│ │ └─ return 0 + 0 + 0 = 0 │ │
│ │ │ │
│ ├─ RIGHT: dfs(5, 4) ──────────────────────┐ │
│ │ │ │
│ │ Level 2: dfs(5, 4) │ │
│ │ │ │ │
│ │ ├─ node = 5, pathMax = 4 │ │
│ │ ├─ Is good? 5 >= 4? YES → count = 1 ✓ │ │
│ │ ├─ newMax = max(4, 5) = 5 │ │
│ │ │ │ │
│ │ ├─ LEFT: dfs(null, 5) → return 0 │ │
│ │ ├─ RIGHT: dfs(null, 5) → return 0 │ │
│ │ │ │ │
│ │ └─ return 1 + 0 + 0 = 1 │ │
│ │ │ │
│ └─ return 1 + 0 + 1 = 2 │ │
│ │
└─ return 1 + 1 + 2 = 4 │
═══════════════════════════════════════════════════
FINAL RESULT: 4 GOOD NODES
═══════════════════════════════════════════════════
Good nodes: 3(root), 4, 3(left-left), 5
Not good: 1(left), 1(right-left)
Path Maximum Tracking:
Visualize pathMax at each node:
3 (pathMax=3, good!)
/ \
(max=3) 1 4 (pathMax=3, good!)
/ / \
(max=3) 3 1 5 (pathMax=4, good!)
(good!) (not good)
Path maximum increases as we go DOWN
when we encounter larger values!
Node 4: Updates max from 3 to 4
Node 5: Compares with 4, is good!
Node 1 (right-left): Compares with 4, not good!
🔍 Step-by-Step Path Analysis
Following Specific Paths:
PATH 1: Root → Left → Left
═══════════════════════════════════
Step 1: At node 3 (root)
Path so far: [3]
pathMax: 3
3 >= 3? YES → GOOD ✓
newMax: 3
Step 2: At node 1 (left)
Path so far: [3, 1]
pathMax: 3
1 >= 3? NO → NOT GOOD ✗
newMax: max(3, 1) = 3
Step 3: At node 3 (left-left)
Path so far: [3, 1, 3]
pathMax: 3
3 >= 3? YES → GOOD ✓
Result for this path: 2 good nodes (nodes 3 and 3)
═══════════════════════════════════
PATH 2: Root → Right → Right
═══════════════════════════════════
Step 1: At node 3 (root)
Path: [3]
pathMax: 3
3 >= 3? YES → GOOD ✓
newMax: 3
Step 2: At node 4 (right)
Path: [3, 4]
pathMax: 3
4 >= 3? YES → GOOD ✓
newMax: max(3, 4) = 4 ← MAX INCREASES!
Step 3: At node 5 (right-right)
Path: [3, 4, 5]
pathMax: 4 ← Using updated max!
5 >= 4? YES → GOOD ✓
Result for this path: 3 good nodes (all of them!)
═══════════════════════════════════
PATH 3: Root → Right → Left
═══════════════════════════════════
Step 1: At node 3 (root)
Path: [3]
pathMax: 3
3 >= 3? YES → GOOD ✓
Step 2: At node 4 (right)
Path: [3, 4]
pathMax: 3
4 >= 3? YES → GOOD ✓
newMax: 4
Step 3: At node 1 (right-left)
Path: [3, 4, 1]
pathMax: 4 ← Node 4 increased the max!
1 >= 4? NO → NOT GOOD ✗
Result: 2 good nodes (3 and 4, but not 1)
📊 Complexity Analysis
Time Complexity: O(n)
Visit each node exactly once
At each node: O(1) operations
- Comparison
- Math.max
- Addition
Total: n × O(1) = O(n)
Space Complexity: O(h)
Recursion call stack: O(h) where h = height
Best case (balanced tree): O(log n)
Worst case (skewed tree): O(n)
No additional data structures used
Just the call stack!
⚠️ Common Mistakes
Mistake 1: Not Updating pathMax
// ❌ WRONG - Always uses initial max
private int dfs(TreeNode node, int pathMax) {
if (node == null) return 0;
int count = (node.val >= pathMax) ? 1 : 0;
// BUG: Not updating pathMax!
int leftGood = dfs(node.left, pathMax); // Still uses old max!
int rightGood = dfs(node.right, pathMax); // Still uses old max!
return count + leftGood + rightGood;
}
// Example: Tree [3, 1, 4]
// At node 4: pathMax = 3, 4 >= 3 → good
// At node 4's children: pathMax still 3!
// But should be 4! Children need updated max! ✗
// ✓ CORRECT - Update before recursing
int newMax = Math.max(pathMax, node.val);
int leftGood = dfs(node.left, newMax); ✓
int rightGood = dfs(node.right, newMax); ✓
Mistake 2: Using Global Maximum
// ❌ WRONG - Uses global max instead of path max
private int maxSoFar = Integer.MIN_VALUE;
private int dfs(TreeNode node) {
if (node == null) return 0;
maxSoFar = Math.max(maxSoFar, node.val); // Global!
int count = (node.val >= maxSoFar) ? 1 : 0;
return count + dfs(node.left) + dfs(node.right);
}
// Problem: maxSoFar is GLOBAL across ALL paths!
// Tree: 3
// / \
// 1 4
// /
// 3
//
// When we reach left node 3:
// maxSoFar already includes 4 from right path! ✗
// But path to node 3 doesn't go through 4!
//
// We need PATH maximum, not GLOBAL maximum! 🎯
// ✓ CORRECT - Use parameter for path-specific max
private int dfs(TreeNode node, int pathMax) { ✓
Mistake 3: Wrong Comparison
// ❌ WRONG - Using > instead of >=
int count = (node.val > pathMax) ? 1 : 0; // > is wrong!
// Problem: Equal values should be good!
// Tree: 3
// /
// 3
//
// At second node 3:
// pathMax = 3
// 3 > 3? NO → count = 0 ✗
// But 3 >= 3? YES → should be good! ✓
// ✓ CORRECT - Use >=
int count = (node.val >= pathMax) ? 1 : 0; ✓
Mistake 4: Not Handling Negative Values
// ❌ WRONG - Starting with 0 as initial max
return dfs(root, 0); // Assumes all values positive!
// Problem: What if root.val is negative?
// Tree: [-1, -2, -3]
//
// At root -1:
// pathMax = 0
// -1 >= 0? NO → count = 0 ✗
// But root is ALWAYS good! ✓
// ✓ CORRECT - Start with root value or MIN_VALUE
return dfs(root, root.val); ✓
// or
return dfs(root, Integer.MIN_VALUE); ✓
Mistake 5: Modifying pathMax Incorrectly
// ❌ WRONG - Updating pathMax even if node not good
private int dfs(TreeNode node, int pathMax) {
if (node == null) return 0;
int count = (node.val >= pathMax) ? 1 : 0;
// BUG: Always updates pathMax
pathMax = node.val; // WRONG!
return count + dfs(node.left, pathMax) + dfs(node.right, pathMax);
}
// Problem: If node.val < pathMax, shouldn't override!
// Tree: 5
// /
// 3
//
// At node 3:
// pathMax = 5
// 3 >= 5? NO, not good
// Then sets pathMax = 3 ✗
// But children should still compare with 5!
// ✓ CORRECT - Use Math.max to keep higher value
int newMax = Math.max(pathMax, node.val); ✓
🎯 Pattern Recognition - Path Property Problems
Core Pattern: DFS with Path Information
Template for path-dependent problems:
dfs(node, pathInfo):
if node is null: return baseValue
// Check property using pathInfo
result = checkProperty(node, pathInfo)
// Update pathInfo for children
newPathInfo = updateInfo(pathInfo, node)
// Recurse with updated info
leftResult = dfs(node.left, newPathInfo)
rightResult = dfs(node.right, newPathInfo)
// Combine results
return combine(result, leftResult, rightResult)
Related Problems:
1. Binary Tree Paths (Problem 137)
Track path as we go
Pass path list/string to children
Collect complete paths at leaves
Same pattern: path information down!
2. Path Sum (Problem 135)
Track sum so far
Pass remaining target to children
Check if reaches 0 at leaf
Same pattern: accumulate as we go!
3. Maximum Path Sum
Track path sum
Update global maximum
Pass path to children
Same pattern: path tracking!
4. Longest Univalue Path
Track current value
Pass to children
Count consecutive same values
Same pattern: path property!
5. Sum Root to Leaf Numbers
Build number as we go down
Pass accumulated number to children
Add at leaves
Same pattern: path accumulation!
When to Use This Pattern:
✓ Property depends on path from root
✓ Need to track information down the tree
✓ Each path is independent
✓ DFS with parameter passing
✓ Path maximum, sum, or other aggregate
📝 Quick Revision Notes
🎯 Core Concept
Good node = node where node.val >= all ancestors. Track path maximum as we traverse. At each node: (1) check if node.val >= pathMax (if yes, it's good), (2) update newMax = max(pathMax, node.val) for children, (3) recurse with newMax. DFS returns count of good nodes in subtree. Root always good!
⚡ Quick Implementation
// Main function
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public int goodNodes(TreeNode root) {
// Approach - DFS
return recursiveDFS(root, root.val);
}
private int recursiveDFS(TreeNode root, int currMax) {
// base case - if leaf node, no contribution.
if(root == null) {
return 0;
}
int good = 0;
// There will be always 1 good node which is root.
// Also, when first time call is made, root value is passed.
// Second time, root value gets compared with its left and right child
if(root.val >= currMax) {
good = 1;
}
// update currMax for children
currMax = Math.max(currMax, root.val);
// good nodes coming from left subtree
int leftCount = 0;
if(root.left != null) {
leftCount = recursiveDFS(root.left, currMax);
}
// good nodes coming from right subtree
int rightCount = 0;
if(root.right != null) {
rightCount = recursiveDFS(root.right, currMax);
}
return good + leftCount + rightCount;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.goodNodes(TreeNode.buildTree(new Integer[] {3,1,4,3,null,1,5}))); // 4
System.out.println(s.goodNodes(TreeNode.buildTree(new Integer[] {3,3,null,4,2}))); // 3
System.out.println(s.goodNodes(TreeNode.buildTree(new Integer[] {1}))); // 1
System.out.println(s.goodNodes(TreeNode.buildTree(new Integer[] {2,null,4,10,8,null,null,4}))); // 4
}
}
🔑 Key Insights
Path Maximum Evolution:
As we go DOWN the tree, pathMax can only:
- Stay the same (if current node smaller)
- Increase (if current node larger)
Never decreases!
Example path: 3 → 1 → 5
At 3: pathMax = 3
At 1: pathMax = max(3,1) = 3 (stayed same)
At 5: pathMax = max(3,5) = 5 (increased!)
This makes sense: we're adding nodes to the path,
so maximum can only stay or grow! 📈
Why Use Math.max:
newMax = Math.max(pathMax, node.val)
Not just: newMax = node.val
Why?
If node.val < pathMax:
Current node NOT good
But children should still compare with old pathMax!
Example:
5
/
3 (not good, 3 < 5)
/
4 (should compare with 5, not 3!)
Math.max keeps the higher value! 🔑
Root Always Good:
Root has no ancestors!
So trivially: root >= all ancestors (none exist)
Root ALWAYS counted as good!
This is why we can start with:
dfs(root, root.val)
root.val >= root.val → always true! ✓
🎪 Memory Aid
"Good = Max on path!"
"Track max DOWN the tree!"
"Use Math.max to update!"
"Root always good!" ✨
⚠️ Don't Forget
- Use >= not > (equal values are good!)
- Update max for children (Math.max!)
- Start with root.val (or MIN_VALUE)
- Return count + left + right (aggregate!)
- Root always good (no ancestors!)
- Path-specific max (not global!)
🎉 Congratulations!
You've mastered path-dependent tree problems!
What You Learned:
✅ Good node definition - Max on path
✅ Path tracking - Passing info down
✅ DFS with parameters - Propagating state
✅ Aggregation - Combining subtree results
✅ Math.max pattern - Maintaining maximum
✅ Path-based reasoning - Independent paths
The Pattern Power:
This pattern applies to MANY problems:
Path Sum → Track sum
Good Nodes → Track max
Path Count → Track path
Univalue Path → Track value
All use same structure:
- DFS with parameter
- Check at node
- Update for children
- Aggregate results
One pattern → Many problems! 🧰
Interview Mastery:
Interviewer: "Count good nodes"
Your thought process:
1. "Good = max on path" ✓
2. "Track pathMax in DFS" ✓
3. "Compare, update, recurse" ✓
4. "Aggregate counts" ✓
5. Code in 5 minutes ✓
Shows strong tree fundamentals! 💪
You're crushing path-based problems! 🌳✨🎯