LC1448 Count Good Nodes in Binary Tree 🟡

A classic Tree problem — we still use DFS, but we "carry some state" with us as we walk.

1. Problem Decoding

We have one Binary Tree.
A "Good Node" means: on the path from Root down to the current Node, nothing has a value strictly greater than it (i.e. its value is ≥ the maximum seen so far from the start).

Mission: count how many Good Nodes are in the tree.

2. Mental Model

Picture walking down the Tree as "hiking and logging the tallest tree so far."

• Start at Root holding a "height record book (Max So Far)"
• At every new tree (current Node), compare its height to the book
• If this tree is "equal to or taller" than the book: it's a Good Node — add 1 point
• Before exploring the next fork: if this tree broke the record, update the book, then carry that book to the left and right children

3. Logic-to-Code Mapping

Write dfs(node, max_so_far) — two inputs: "where you stand" and "the record book." Handle three situations:

Situation 1: Fall off the edge (no Node left)

If you walk off the edge (Null / None), there's nothing to count — return 0.

# Fell off the edge
if not node:
    return 0  # no Good Nodes here

Situation 2: Is this a Good Node?

Compare node.val with max_so_far. If yours is ≥ the record, you pass — score 1 point (else 0).

# Check Good Node
if node.val >= max_so_far:
    good = 1
else:
    good = 0

Situation 3: Update the record, then go left & right

Before diving into children, update max_so_far to the max of "old record" and "current Node." Then return your points + left subtree points + right subtree points.

# Update the record for children
new_max = max(max_so_far, node.val)

# Total = self + left + right
return good + dfs(node.left, new_max) + dfs(node.right, new_max)

4. Step-by-Step Walkthrough

Suppose the Tree looks like this:

        3
       / \
      1   4
     /   / \
    3   1   5

Start (Root) → Node 3 | Book: 3

• Enter Root (3) with the initial record book set to 3 (its own value)
• Check: 3 ≥ 3? → Yes! Good Node (+1)
• Update the book to max(3, 3) = 3, then explore left and right

Left branch → Node 1 | Book: 3

• Arrive at 1 carrying book value 3
• Check: 1 ≥ 3? → No! (0 points)
• Update the book to max(3, 1) = 3 (record stays 3), then go left

End of left branch → Node 3 | Book: 3

• Arrive at 3 carrying book value 3
• Check: 3 ≥ 3? → Yes! Good Node (+1)
• Leaf — return up. The whole left side scored 1 point

Right of Root → Node 4 | Book: 3

• Back at Root, go right to 4 carrying book value 3 (Root's record)
• Check: 4 ≥ 3? → Yes! Good Node (+1)
• Update the book to max(3, 4) = 4 (new record!) and carry 4 to both children

End of right branch → Nodes 1 and 5 | Book: 4

• Left child 1 vs book 4: 1 ≥ 4 → No! (0 points)
• Right child 5 vs book 4: 5 ≥ 4 → Yes! Good Node (+1)
• The whole right side scored 2 points

Total: Root (1) + left (1) + right (2) = 4 Good Nodes

5. Full Assembled Code (Clean Code)

Glue the pieces together — Python can collapse the Good check into one line:

# 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:

        # Hike + log the height record (DFS)
        def dfs(node, max_so_far):
            # 1. Fall off the edge
            if not node:
                return 0

            # 2. Good Node? (1 point or 0)
            good = 1 if node.val >= max_so_far else 0

            # 3. Update the record book
            new_max = max(max_so_far, node.val)

            # 4. Self + left + right
            return good + dfs(node.left, new_max) + dfs(node.right, new_max)

        # Start at Root with the first record = Root's own value
        return dfs(root, root.val)

6. Complexity Analysis

• Time Complexity: O(N) where N is the node count — we visit every node once
• Space Complexity: O(H) where H is tree height (Call Stack). Worst case (a straight line) is O(N)