LeetCode 1448 - Count Good Nodes in Binary Tree

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree and asks us to count how many nodes are considered "good".

A node is called good if, along the path from the root to that node, there is no node with a value greater than the current node's value. In other words, the current node must be greater than or equal to every value seen earlier on the path from the root.

For example, suppose the path from the root to a node is:

3 -> 1 -> 3

The final node with value 3 is good because the maximum value encountered along the path is also 3. There is no earlier node with a value larger than it.

However, in this path:

3 -> 3 -> 2

The node with value 2 is not good because the value 3 already appeared earlier in the path, and 3 > 2.

The input is a binary tree where each node contains:

an integer value
a left child pointer
a right child pointer

The output is a single integer representing the total number of good nodes in the entire tree.

The constraints are important:

The tree can contain up to 10^5 nodes
Node values range from -10^4 to 10^4

These constraints tell us that:

We need an algorithm that is close to linear time
Recomputing information repeatedly for every node could become too slow
Recursive depth may become large for highly skewed trees

Several edge cases are worth considering immediately.

A tree with only one node should return 1, because the root is always good. A completely decreasing path, such as 5 -> 4 -> 3 -> 2, should count only the root. A completely increasing path should count every node. Negative values also matter because the comparison logic must work regardless of sign.

The problem guarantees that the tree has at least one node, so we never need to handle an empty input tree.

Approaches

Brute Force Approach

The brute force idea is to evaluate each node independently.

For every node in the tree, we can trace the path from the root to that node and determine the maximum value encountered along that path. If the node's value is at least that maximum, then the node is good.

One possible implementation is:

For each node, reconstruct the path from the root
Scan all values in that path
Determine whether the node is good

This works correctly because it directly follows the problem definition.

However, it is inefficient. In the worst case, the tree could be completely skewed, behaving like a linked list. Then, for each node, we may need to traverse almost the entire height of the tree again.

For a tree with n nodes:

Each node may require O(n) work
Total complexity becomes O(n^2)

With 10^5 nodes, this is too slow.

Optimal Approach

The key observation is that while traversing from the root downward, we only need one piece of information:

The maximum value seen so far on the current path.

When we visit a node:

If node.val >= max_so_far, the node is good
We then update:

new_max = max(max_so_far, node.val)

This updated maximum is passed to the children

This eliminates repeated work because each node is processed exactly once.

Depth-First Search works naturally here because the problem depends on root-to-node paths. During DFS traversal, we always know the current path information.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Recomputes path maximum repeatedly
Optimal	O(n)	O(h)	Tracks path maximum during DFS traversal

Here:

n is the number of nodes
h is the tree height

Algorithm Walkthrough

Optimal DFS Algorithm

Start a Depth-First Search from the root node.

The root is always good because there are no earlier nodes on its path. 2. Maintain a variable called max_so_far.

This variable represents the maximum value encountered from the root to the current node. 3. At each node, compare the node's value with max_so_far.

If:

node.val >= max_so_far

then the current node is good, so increment the answer. 4. Update the maximum value for the subtree.

The children inherit the maximum value seen along the path:

updated_max = max(max_so_far, node.val)

Recursively process the left subtree using updated_max.
Recursively process the right subtree using updated_max.
When a null node is reached, return 0.

Null nodes do not contribute to the count. 8. Sum the counts from:

the current node
the left subtree
the right subtree

Return the final total.

Why it works

The algorithm maintains a critical invariant:

max_so_far always equals the maximum node value on the path from the root to the current node.

Because of this invariant, checking whether a node is good becomes a simple comparison against max_so_far.

Every node is visited exactly once, and the correct path maximum is always available during traversal. Therefore, every node is classified correctly as either good or not good.

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

from typing import Optional

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node: Optional[TreeNode], max_so_far: int) -> int:
            if not node:
                return 0

            good = 1 if node.val >= max_so_far else 0

            updated_max = max(max_so_far, node.val)

            left_good = dfs(node.left, updated_max)
            right_good = dfs(node.right, updated_max)

            return good + left_good + right_good

        return dfs(root, root.val)

The implementation uses a recursive DFS helper function.

The helper function receives:

the current node
the maximum value seen on the current root-to-node path

The base case handles null nodes by returning 0.

For each valid node:

We determine whether it is good
We update the running maximum
We recursively process both children

The recursive calls return the number of good nodes in each subtree, and the current node's contribution is added to that total.

The initial call starts with:

dfs(root, root.val)

because the root itself defines the initial maximum.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func goodNodes(root *TreeNode) int {
    var dfs func(node *TreeNode, maxSoFar int) int

    dfs = func(node *TreeNode, maxSoFar int) int {
        if node == nil {
            return 0
        }

        good := 0
        if node.Val >= maxSoFar {
            good = 1
        }

        updatedMax := maxSoFar
        if node.Val > updatedMax {
            updatedMax = node.Val
        }

        leftGood := dfs(node.Left, updatedMax)
        rightGood := dfs(node.Right, updatedMax)

        return good + leftGood + rightGood
    }

    return dfs(root, root.Val)
}

The Go solution follows the same logic as the Python version.

Some Go-specific details are important:

nil is used instead of None
Go does not provide a built-in max function for integers, so the maximum update is written manually
Recursive closures require declaring the variable first:

var dfs func(...)

The algorithm and complexity remain identical.

Worked Examples

Example 1

Input:

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

Tree:

Traversal process:

Node	max_so_far	Good?	Updated Max	Total Good
3	3	Yes	3	1
1	3	No	3	1
3	3	Yes	3	2
4	3	Yes	4	3
1	4	No	4	3
5	4	Yes	5	4

Final answer:

Example 2

Input:

root = [3,3,null,4,2]

Tree:

Traversal process:

Node	max_so_far	Good?	Updated Max	Total Good
3	3	Yes	3	1
3	3	Yes	3	2
4	3	Yes	4	3
2	3	No	3	3

Final answer:

Example 3

Input:

root = [1]

Tree:

Traversal process:

Node	max_so_far	Good?	Updated Max	Total Good
1	1	Yes	1	1

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack stores one frame per tree level

The DFS traversal processes each node a single time, so the total runtime is linear in the number of nodes.

The space complexity depends on the tree height:

Balanced tree: O(log n)
Skewed tree: O(n)

This space usage comes entirely from recursion depth.

Test Cases

# Helper TreeNode class for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    3,
    TreeNode(1, TreeNode(3)),
    TreeNode(4, TreeNode(1), TreeNode(5))
)
assert solution.goodNodes(root1) == 4  # Standard mixed tree

# Example 2
root2 = TreeNode(
    3,
    TreeNode(3, TreeNode(4), TreeNode(2))
)
assert solution.goodNodes(root2) == 3  # One node blocked by larger ancestor

# Example 3
root3 = TreeNode(1)
assert solution.goodNodes(root3) == 1  # Single node tree

# Strictly increasing path
root4 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)
assert solution.goodNodes(root4) == 4  # Every node is good

# Strictly decreasing path
root5 = TreeNode(
    5,
    TreeNode(
        4,
        TreeNode(
            3,
            TreeNode(2)
        )
    )
)
assert solution.goodNodes(root5) == 1  # Only root is good

# Tree with negative values
root6 = TreeNode(
    -1,
    TreeNode(-2),
    TreeNode(0)
)
assert solution.goodNodes(root6) == 2  # Negative values handled correctly

# Duplicate values
root7 = TreeNode(
    2,
    TreeNode(2),
    TreeNode(2)
)
assert solution.goodNodes(root7) == 3  # Equal values are allowed

# Complex mixed tree
root8 = TreeNode(
    8,
    TreeNode(
        3,
        TreeNode(1),
        TreeNode(6, TreeNode(4), TreeNode(7))
    ),
    TreeNode(
        10,
        None,
        TreeNode(14, TreeNode(13))
    )
)
assert solution.goodNodes(root8) == 3  # Only nodes meeting path maximum condition

print("All test cases passed!")

Test	Why
`[3,1,4,3,null,1,5]`	Validates standard example with mixed good and bad nodes
`[3,3,null,4,2]`	Tests equal ancestor values and blocked nodes
`[1]`	Tests smallest possible tree
Increasing chain	Ensures all nodes become good
Decreasing chain	Ensures only root remains good
Negative values	Verifies comparisons work with negatives
Duplicate values	Confirms equality counts as good
Complex mixed tree	Tests deeper recursive traversal

Edge Cases

Single Node Tree

A tree containing only one node is the smallest valid input. The root is always considered good because there are no earlier nodes on the path.

This case can expose bugs in implementations that assume child nodes exist or incorrectly initialize the running maximum.

The implementation handles this naturally because the DFS starts with:

dfs(root, root.val)

The root immediately satisfies:

node.val >= max_so_far

so the answer becomes 1.

Completely Decreasing Tree

Consider a tree like:

5 -> 4 -> 3 -> 2

Only the root should be counted as good.

A buggy implementation might accidentally reset the maximum while traversing downward, causing smaller nodes to be counted incorrectly.

This solution avoids that issue because max_so_far is propagated downward through every recursive call and never decreases.

Duplicate Values

The definition says a node is good if no earlier node has a value greater than it.

That means equal values are allowed.

For example:

2 -> 2 -> 2

All nodes are good.

A common bug is using:

node.val > max_so_far

instead of:

node.val >= max_so_far

The implementation correctly uses >=, ensuring duplicates are counted properly.