LeetCode 1448: Count Good Nodes in Binary Tree with DFS Path Maximum

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

In LeetCode 1448: Count Good Nodes in Binary Tree, we need to determine how many nodes are at least as large as every node that appears before them on the path from the root.

The key observation is that we do not need to remember every ancestor value. We only need one piece of information:

The maximum value seen so far on the current root-to-node path.

This naturally leads to a Depth-First Search (DFS) solution. As we recursively traverse the tree, we carry the current path maximum with us. If the current node is greater than or equal to that maximum, it is a good node.

This problem is a useful example of a common tree pattern:

DFS + state carried from parent to child.

---

Original Problem and Credit

This article is based on the LeetCode problem “1448. Count Good Nodes in Binary Tree.”

• Original problem: LeetCode 1448 - Count Good Nodes in Binary Tree
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

A node is considered good when no node on the path from the root to that node has a value greater than the current node. The task is to count all such nodes.

---

Original Problem in Simple Terms

We are given a binary tree.

For every node, imagine walking from the root down to that node.

The current node is a good node when its value is greater than or equal to every value encountered along that path.

For example, consider this path:

3 → 1 → 5

For node 5, the values before it are:

3, 1

Since:

5 >= 3
5 >= 1

node 5 is good.

Now consider:

3 → 4 → 1

For node 1, there is already an ancestor with value 4.

Since:

1 < 4

node 1 is not good.

The tree contains between 1 and 10^5 nodes, and each node value is between -10^4 and 10^4.

---

Real-World Scenario

Imagine a hypothetical monitoring system where services are organized as a binary dependency tree.

Each service has a performance score.

        3
       / \
      1   4
     /   / \
    3   1   5

A request starts at the root service and travels through dependencies.

We want to identify services whose performance score is at least as high as every service encountered earlier on that request path.

For example:

3 → 4 → 5

Service 5 is a record-high service because:

5 >= 3
5 >= 4

But on:

3 → 4 → 1

service 1 is not a record-high service because service 4 already had a higher score.

The engineering question becomes:

How many services are record-high values along their own root-to-service dependency path?

This is mathematically equivalent to counting good nodes in the original binary tree problem.

---

Examples

Example 1

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

Output:
4

The tree can be visualized as:

        3
       / \
      1   4
     /   / \
    3   1   5

Consider each root-to-node path.

The root:

3

is good because there are no previous nodes.

For node 1:

3 → 1

1 < 3, so it is not good.

For the lower-left 3:

3 → 1 → 3

The maximum value is 3, and the current node also has value 3.

Because equality is allowed:

3 >= 3

this node is good.

For node 4:

3 → 4

4 >= 3, so it is good.

For node 1 under 4:

3 → 4 → 1

1 < 4, so it is not good.

For node 5:

3 → 4 → 5

5 >= 4, so it is good.

Therefore:

Good nodes = 3, 3, 4, 5
Count = 4

---

Example 2

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

Output:
3

The tree is:

        3
       /
      3
     / \
    4   2

The good nodes are:

3
3
4

The node 2 is not good because its path contains a value of 3, which is larger than 2.

---

Example 3: Single Node

Input:
root = [1]

Output:
1

The root is always a good node because there is no ancestor that can have a greater value.

These inputs and expected outputs correspond to the examples published for LeetCode 1448.

---

Mapping to the Original Problem

The hypothetical monitoring scenario maps directly to the binary tree problem:

Nothing about the underlying computational problem changes.

We are still given a binary tree, examining every root-to-node path, and counting nodes whose values are at least the maximum value seen on that path.

---

Solution Intuition

The most important question is:

What information do we actually need when we reach a node?

Suppose the current path is:

3 → 1 → 4 → 2 → X

To determine whether X is good, we could compare X with every previous value:

3
1
4
2

But that would be unnecessary.

The only ancestor that matters is the largest ancestor value.

For this path:

max(3, 1, 4, 2) = 4

Therefore, the decision becomes simply:

X >= 4 ?

If yes, X is good.

If no, it is not.

This means we only need to carry one integer while traversing:

maximum value seen so far

---

Why DFS Fits This Problem

A Depth-First Search (DFS) explores one path of the tree before returning and exploring another path.

That behavior fits perfectly because whether a node is good depends specifically on its own root-to-node path.

Suppose we are at:

        3
       / \
      1   4

When entering the left subtree, the maximum so far is:

3

When entering the right subtree, the maximum also begins as:

3

But after reaching 4, the right path maximum becomes:

4

That information should affect descendants of 4, but it should not affect descendants in the left subtree.

Recursive DFS naturally gives us this behavior because each recursive call carries the state associated with its own path.

---

What Should the Recursive Function Represent?

We define:

int numBig(TreeNode* root, int num)

where:

root

is the node currently being processed, and:

num

represents the maximum value encountered before or at the parent of the current node.

The function returns:

The number of good nodes inside the subtree rooted at root, given the path maximum num.

This definition is important because once the meaning of the recursive function is clear, the rest of the solution follows naturally.

---

Step 1: Handle an Empty Tree

If:

root == nullptr

there is no node to count.

Therefore:

if (root == nullptr) {
    return 0;
}

This is the recursion's base case.

---

Step 2: Determine Whether the Current Node Is Good

The current node is good when:

root->val >= num

Notice that we use:

>=

not:

>

Equality is important.

For example:

3 → 1 → 3

The final 3 is still good because no ancestor is greater than it.

So:

current value = 3
maximum previous value = 3

3 >= 3

means the node qualifies.

---

Step 3: Update the Maximum for the Children

Suppose:

num = 3
root->val = 5

The current node becomes the new largest value on the path.

Therefore, both children should receive:

5

as their path maximum.

That gives:

numBig(root->left, root->val)
numBig(root->right, root->val)

Now consider:

num = 5
root->val = 2

The value 2 does not replace the previous maximum.

The children must still compare themselves against:

5

So we recurse using:

numBig(root->left, num)
numBig(root->right, num)

This is how the algorithm preserves the maximum value along each path.

---

Another Way to Think About the State

Conceptually, every recursive call performs:

newMax = max(previousMax, currentValue)

The supplied implementation expresses this with two branches.

When:

root->val >= num

the current value is the new maximum, so we pass:

root->val

When:

root->val < num

the previous maximum remains unchanged, so we continue passing:

num

Therefore, the code is maintaining exactly the same invariant as:

max(num, root->val)

---

Algorithm

1. Start DFS from the root.

2. Initialize the maximum value seen so far to INT_MIN.

3. If the current node is nullptr, return 0.

4. Compare the current node's value with the maximum value from its path.

5. If:

   current value >= path maximum
   

   then:

   • count the current node as good;
   • the current value becomes the path maximum for its children.

6. Otherwise:

   • do not count the current node;
   • keep the previous path maximum for its children.

7. Recursively process the left subtree.

8. Recursively process the right subtree.

9. Return the current node's contribution plus the results from both subtrees.

---

Why Start with INT MIN?

The root should always be counted as a good node.

We call:

numBig(root, INT_MIN);

Since every valid node value is greater than or equal to INT_MIN, the root satisfies:

root->val >= INT_MIN

and is counted.

This avoids needing a separate special case for the root.

Conceptually:

Before visiting the root:
maximum seen = negative infinity

Then any possible root value becomes the first maximum.

---

Why the Algorithm Works

The key invariant is:

When numBig(node, num) begins, num stores the largest value encountered on the path before the current node.

Consider the two possibilities.

Case 1: root->val >= num

The current node is at least as large as every previous node on the path.

Therefore, it is good.

Since it is also now the largest value on the path, its children should compare themselves against:

root->val

So we count one node and recurse with the new maximum:

1
+ numBig(root->left, root->val)
+ numBig(root->right, root->val)

Case 2: root->val < num

Some ancestor already has a greater value.

Therefore, the current node cannot be good.

The current node also cannot become the new maximum, so the maximum remains:

num

We therefore recurse with:

numBig(root->left, num)
+ numBig(root->right, num)

Final Result

DFS eventually visits every node exactly once.

Each node is counted if and only if its value is at least the maximum value appearing before it on its root-to-node path.

Therefore, the total returned by the root call is exactly the number of good nodes.

---

Complexity Analysis

Let:

n = number of nodes in the binary tree

Time Complexity

O(n)

Every tree node is visited exactly once.

For each node, we perform only constant-time operations:

• check whether the node is nullptr;
• compare two integers;
• add the results of recursive calls;
• make at most two recursive calls.

So the total work is proportional to the number of nodes:

O(n)

---

Space Complexity

The algorithm does not create a separate data structure containing all nodes.

However, recursive DFS uses the program's call stack.

If:

h = height of the tree

the auxiliary space complexity is:

O(h)

For a balanced binary tree:

h = O(log n)

so the recursion stack uses:

O(log n)

In the worst case, the tree can be completely skewed:

1
 \
  2
   \
    3
     \
      4
       \
        ...

Then:

h = n

and the worst-case auxiliary space complexity becomes:

O(n)

Therefore:

Time:  O(n)
Space: O(h), worst case O(n)

---

Corrected Solution: Recursive DFS with Path Maximum

#include <climits>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right)
 *         : val(x), left(left), right(right) {}
 * };
 */

class Solution {

private:

    int numBig(TreeNode* root, int num) {

        if (root == nullptr) {
            return 0;
        }

        int res;

        if (root->val >= num) {

            res = 1
                + numBig(root->left, root->val)
                + numBig(root->right, root->val);

        } else {

            res = numBig(root->left, num)
                + numBig(root->right, num);
        }

        return res;
    }

public:

    int goodNodes(TreeNode* root) {

        return numBig(root, INT_MIN);
    }
};

---

Walkthrough

Consider:

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

The tree is:

        3
       / \
      1   4
     /   / \
    3   1   5

We begin with:

numBig(root, INT_MIN)

Visit Root 3

Current state:

node = 3
num = INT_MIN

Check:

3 >= INT_MIN

Yes.

So 3 is good.

The new path maximum becomes:

3

Current count:

1

---

Visit Left Node 1

Path:

3 → 1

State:

node = 1
num = 3

Check:

1 >= 3

No.

So this node is not counted.

The maximum remains:

3

---

Visit Lower-Left Node 3

Path:

3 → 1 → 3

State:

node = 3
num = 3

Check:

3 >= 3

Yes.

This node is good.

Notice again why equality matters.

Current good nodes from this side:

3 (root)
3 (lower-left)

---

Visit Right Node 4

Return to the root and explore the other branch:

3 → 4

State:

node = 4
num = 3

Check:

4 >= 3

Yes.

So 4 is good.

Because 4 is now the largest value on this path, its children receive:

num = 4

---

Visit Node 1 Under 4

Path:

3 → 4 → 1

State:

node = 1
num = 4

Check:

1 >= 4

No.

The node is not good.

---

Visit Node 5

Path:

3 → 4 → 5

State:

node = 5
num = 4

Check:

5 >= 4

Yes.

So 5 is good.

---

Final Count

The good nodes are:

3
3
4
5

Therefore:

answer = 4

---

Common Mistakes

1. Using > Instead of >=

A node can have the same value as the maximum ancestor and still be good.

Incorrect:

if (root->val > num)

Correct:

if (root->val >= num)

For example:

3 → 3

The second 3 is good because there is no ancestor greater than 3.

---

2. Comparing Only With the Parent

Consider:

       5
      /
     2
    /
   4

If we only compare 4 with its parent:

4 > 2

we might incorrectly classify it as good.

But the complete path is:

5 → 2 → 4

and:

4 < 5

Therefore, 4 is not good.

This is why we must remember the maximum value across the entire path, not just the parent.

---

3. Replacing the Maximum With a Smaller Value

Suppose:

5 → 2

When we reach 2, we must not change the path maximum from 5 to 2.

The descendants of 2 still have 5 as an ancestor.

The state must represent:

max(all values seen on the path)

not simply:

value of the parent

---

4. Forgetting That the State Is Path-Specific

The left and right subtrees can develop different path maximums.

For example:

        3
       / \
      8   4

After entering the left subtree:

maximum = 8

But that should not affect the right subtree.

The right subtree's path is:

3 → 4

not:

3 → 8 → 4

Recursive DFS handles this naturally because each branch receives its own function argument.

---

5. Forgetting the Null Base Case

Without:

if (root == nullptr) {
    return 0;
}

the recursion would eventually attempt to access:

root->val

when root is null.

That would result in invalid memory access.

---

Key Takeaways

1. Look for the minimum state required from the ancestors.
   We do not need the complete root-to-node path. We only need its maximum value.

2. DFS is useful when information follows a path.
   Each recursive call can carry state from the parent to the child.

3. Maintain a clear recursive invariant.
   Here, the important invariant is that num represents the maximum value seen on the path before the current node.

4. Equality matters.
   A node is good when:

   current value >= path maximum
   

   not only when it is strictly greater.

5. Recursive tree algorithms often use O(h) stack space.
   The worst case is O(n) for a completely skewed tree.

The central pattern to remember is:

Traverse the tree
        +
carry information from ancestors
        +
update that information for each child

For this problem, that information is simply:

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