Introduction

Good Node means:

  • current node value
  • is greater than or equal to
  • every previous node
    in root-to-node path

Condition:

node.value >= maximum value seen in path

Example:

        3
      /   \
     1     4
    /     / \
   3     1   5

Good Nodes:
3 4 5 3

Count:
4

Explanation:

Every good node maintains maximum value in current path.

This problem is one of the most important applications of:

DFS Traversal

Constraints

 1 <= Number of Nodes <= 10^5

Approach : Recursive DFS Solution

Explanations:

Explanation:

The idea is:

  • traverse tree using DFS
  • maintain maximum value
    in current path

Steps:

  1. Visit current node.
  2. Compare node with path maximum.
  3. Count node if valid.
  4. Update maximum value.
  5. Recurse left subtree.
  6. Recurse right subtree.

Condition:

current.value >= pathMaximum

This approach:

  • uses DFS recursion
  • tracks maximum value dynamically

Dry Run

Visit:3

Path maximum:
3

Good node count:
1

Visit:
4

Updated maximum:
4

Good node count:
2

Visit:
5

Updated maximum:
5

Good node count:
3

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Every tree node is visited once.

Space Complexity:- O(h)
Explanation :
Recursion stack depends on tree height.

Why This Problem is Important

This problem builds the foundation for:

  • DFS traversal
  • Path tracking
  • Recursive tree processing
  • Maximum value propagation
  • Binary tree analysis

Real-World Applications

Good node concepts are used in:

  • Path optimization
  • Decision trees
  • Hierarchical analysis
  • Network routing
  • Graph processing systems

Common Beginner Mistakes

  • Forgetting path maximum update
  • Incorrect comparison logic
  • Wrong recursion flow
  • Missing base case
  • Passing incorrect maximum value

Interview Tip

Interviewers often expect:

  • DFS understanding
  • recursion explanation
  • path tracking logic
  • maximum propagation clarity

Always explain:

  • path maximum update
  • recursive traversal
  • good node validation logic

Related Questions

  • Maximum Depth of Binary Tree
  • Diameter of Binary Tree
  • Lowest Common Ancestor
  • Balanced Binary Tree
  • DFS Traversal

Final Takeaway

The Count Good Nodes problem is one of the most important beginner DFS tree problems.

It teaches:

  • DFS recursion
  • path tracking
  • maximum value propagation
  • recursive tree processing

Understanding this problem builds a strong foundation for:

  • advanced tree problems
  • graph traversal
  • interview-level algorithms.