Description

Given the root of a binary tree, return the number of good nodes.

A node X is considered good if there are no nodes with a value greater than X on the path from the root to that node.

In other words, a node is good if its value is greater than or equal to every node that came before it on the path from the root.

Example

Example 1

Input:  root = [2,1,1,3,null,1,5]
Output: 3

The good nodes are:

  • 2 (the root is always good)
  • 3 (greater than every value on its path)
  • 5 (greater than every value on its path)

Example 2

Input:  root = [1,2,-1,3,4]
Output: 4

Key Observation

For every node, we only care about one piece of information:

What is the maximum value we've seen from the root to this node?

If the current node's value is greater than or equal to this maximum, then it is a good node.

After visiting the node, we update the maximum before exploring its children.

Root → Left → Left

Values:
2 → 1 → 3

Maximums:
2 → 2 → 3

Notice that every recursive call (or stack entry) has its own maximum value.

Approach 1 — Iterative DFS (Stack)

Instead of recursion, we explicitly maintain our own stack.

Each stack entry stores:

  • the current node
  • the maximum value seen on the path to that node
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        if not root:
            return 0

        res = 0
        stack = [(root, root.val)]

        while stack:
            node, currMax = stack.pop()

            if node.val >= currMax:
                res += 1

            newMax = max(node.val, currMax)

            if node.left:
                stack.append((node.left, newMax))

            if node.right:
                stack.append((node.right, newMax))

        return res

How it works

Suppose the tree is

        3
       / \
      1   4
     /
    5

Initially:

stack = [(3,3)]

Pop:

(3,3)

3 >= 3 ✔
answer = 1

Push children:

(1,3)
(4,3)

Process (4,3):

4 >= 3 ✔
answer = 2

Process (1,3):

1 >= 3 ✘

Push:

(5,3)

Process (5,3):

5 >= 3 ✔
answer = 3

Done.

Complexity

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

Where:

  • n = number of nodes
  • h = height of the tree

The stack never stores more than one path through the tree (plus pending siblings), so the average auxiliary space is proportional to the tree height. In a completely skewed tree, the height becomes n, giving a worst-case space complexity of O(n).

Approach 2 — Recursive DFS with Global Variable

Instead of maintaining the answer locally, we keep a class variable.

class Solution:
    def goodNodes(self, root: TreeNode) -> int:

        self.res = 0

        def dfs(node, maxVal):
            if not node:
                return

            if node.val >= maxVal:
                self.res += 1

            currMax = max(node.val, maxVal)

            dfs(node.left, currMax)
            dfs(node.right, currMax)

        dfs(root, root.val)

        return self.res

Idea

Each recursive call receives the maximum value seen so far.

dfs(node, maxVal)

For every node:

  1. Check whether it's good.
  2. Update the maximum.
  3. Visit left subtree.
  4. Visit right subtree.

This is probably the most intuitive recursive solution.

Complexity

  • Time: O(n)
  • Space: O(h) average, O(n) worst case (recursive call stack)

Approach 3 — Pure Recursive DFS (Recommended)

Instead of using a global variable, every recursive call simply returns the number of good nodes in its subtree.

class Solution:
    def goodNodes(self, root: TreeNode) -> int:

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

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

            currMax = max(node.val, maxVal)

            return (
                good
                + dfs(node.left, currMax)
                + dfs(node.right, currMax)
            )

        return dfs(root, root.val)

This version is cleaner because:

  • no global state
  • each function has a single responsibility
  • easy to reason about
  • easy to test

Complexity

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

Why This Works

The important realization is that each node only depends on the path leading to it.

We don't care about:

  • sibling nodes
  • cousins
  • the rest of the tree

We only need one piece of information:

What is the largest value I've seen on my path from the root?

That single value is enough to determine whether the current node is good.

        4
       / \
      2   6
     / \
    5   1

Path to 5

4 → 2 → 5

Maximum so far:
4 → 4 → 5

Since 5 >= 4, it's a good node.

Interview Takeaways

  • Recognize that this is a DFS traversal problem.
  • Carry the maximum value seen so far as additional state.
  • Every recursive call (or stack entry) maintains its own path maximum.
  • You only visit each node once, making the solution O(n).
  • In interviews, both the recursive DFS and iterative DFS solutions are considered optimal. The pure recursive version that returns the count directly is often the cleanest because it avoids mutable global state while keeping the logic concise.

Final Thoughts

This is an excellent example of a DFS problem where the trick is not the traversal itself, but what information you carry along the path. By passing the maximum value seen so far, each node can determine independently whether it is "good," resulting in a simple and efficient O(n) solution.