Count Good Nodes in a Binary Tree – LeetCode75 Python Solution Explained

The Count Good Nodes in a Binary Tree problem (LeetCode75) is an insightful challenge for binary tree enthusiasts and coding interview candidates. It helps you understand tree traversal, recursion and path tracking while practicing conditional logic in a tree structure.

In this blog, we’ll break down the problem, provide examples, explain a Python solution step by step, analyze time and space complexity and discuss real-world applications.

Problem Statement

A node in a binary tree is called good if on the path from the root to that node, there are no nodes with a value greater than that node.

Your task: Given the root of a binary tree, return the number of good nodes in the tree.

Example 1

Input:

Output:

Explanation:

Good nodes are 3 (root), 3 (left leaf), 4 (right child), 5 (right-right leaf).
Node 1 under root and node 1 under 4 are not good nodes.

Example 2

Input:

root = [3]

Output:

Explanation: Only the root exists, which is always a good node.

Understanding the Problem

Key points:

A node is good if no node on the path from the root to it has a higher value.
We can solve this efficiently using DFS recursion while keeping track of the maximum value seen so far.
Compare each node with the maximum value along its path to determine if it’s good.

Complete Python Solution

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_val):
            if not node:
                return 0
            
            # Check if the current node is good
            is_good = node.val >= max_val
            # Update max_val along the path
            max_val = max(max_val, node.val)

            # Traverse left and right subtrees
            left_good_nodes = dfs(node.left, max_val)
            right_good_nodes = dfs(node.right, max_val)

            # Return total good nodes in this subtree
            return is_good + left_good_nodes + right_good_nodes
        
        # Start DFS from root with initial max value as negative infinity
        return dfs(root, float('-inf'))

Step-by-Step Explanation with Code

Step 1: Define DFS Function

We define a helper function dfs(node, max_val) to traverse the tree recursively and track the maximum value along the current path.

def dfs(node, max_val):
    if not node:
        return 0

Step 2: Determine if Node is Good

A node is good if its value is greater than or equal to the maximum value along the path.

is_good = node.val >= max_val
max_val = max(max_val, node.val)

Step 3: Traverse Left and Right Subtrees

left_good_nodes = dfs(node.left, max_val)
right_good_nodes = dfs(node.right, max_val)

Recursively calculate the number of good nodes in both left and right subtrees.

Step 4: Aggregate Results

return is_good + left_good_nodes + right_good_nodes

Sum the good nodes from the current node and its subtrees.

Step 5: Initialize DFS from Root

return dfs(root, float('-inf'))

Start DFS from the root node with negative infinity as the initial maximum value to ensure the root is always counted as a good node.

Time and Space Complexity

Time Complexity:O(n)
- Every node is visited once.
Space Complexity:O(h)
- h is the height of the tree due to recursion stack.
- Worst-case skewed tree: h = n
- Balanced tree: h = log(n)

Edge Cases

Empty Tree: No nodes → return 0.
Single Node Tree: Root is always good → return 1.
All Nodes Increasing: All nodes good.
All Nodes Decreasing: Only the root is good.

Real-World Applications

Path Maximum Tracking: Useful in algorithms requiring comparison along hierarchical paths.
Tree-based Decision Making: Good nodes could represent optimal decision points in a decision tree.
Gaming or Simulation Trees: Identify nodes with maximum values along paths in strategy trees.
Data Analysis: Track local maxima in hierarchical datasets.

Conclusion

The Count Good Nodes in a Binary Tree problem is a classic recursion and DFS challenge. It strengthens your understanding of:

Recursive tree traversal
Conditional checks along a path
Aggregating results from subtrees

Mastering this problem prepares you for advanced tree questions, coding interviews and real-world hierarchical data analysis.

References

LeetCode 1448 – Count Good Nodes in a Binary Tree – Official problem page with examples and submissions.
Programiz – Binary Tree in Python – Python implementation of binary trees and traversal techniques.
Wikipedia – Binary Tree – Overview of binary tree concepts, properties, and applications.