Count Good Nodes LeetCode 1448 Guide

LeetCode 1448 — Count Good Nodes in Binary Tree — gives you the root of a binary tree and asks you to count all "good" nodes. A node X is considered good if no node on the path from the root to X has a value greater than X's value. In other words, the node must be at least as large as every ancestor on its path from the root.

This problem is labeled Medium and is an excellent introduction to the "pass information downward" pattern in tree DFS. Unlike problems where information bubbles up from leaves, this one passes a running maximum down from parent to child, illustrating a different but equally important recursive technique.

The constraints guarantee the tree has between 1 and 100,000 nodes, with node values ranging from -10,000 to 10,000. Since values can be negative, it is important to initialize the running maximum correctly — starting with negative infinity works, but starting with the root value and counting the root explicitly is cleaner.

The key insight is that whether a node is "good" depends entirely on the path from the root to that node — specifically the maximum value seen along that path. If we pass this running maximum as a parameter into each recursive call, we can decide instantly whether the current node qualifies as good.

At each node, compare node.val against maxSoFar. If node.val >= maxSoFar, the node is good — increment the count. Then update the maximum for the children: newMax = max(maxSoFar, node.val). This ensures children see the correct maximum for their path from the root.

This is a preorder traversal: we process the current node before recursing into its children. The direction of information flow — from root toward leaves via function parameters — distinguishes this from postorder problems where information flows upward via return values.

The recursive helper function dfs(node, maxSoFar) encapsulates the entire logic. The base case returns 0 when node is null — we have fallen off the tree and there are no good nodes to count. Otherwise, determine if the current node is good, update the running maximum, and recurse into both subtrees.

The count at each node is either 0 or 1 (not good or good). Adding dfs(left, newMax) and dfs(right, newMax) accumulates the total count from all descendants. The final return value from the initial call on the root is the total number of good nodes in the entire tree.

Python code: def goodNodes(root): def dfs(node, maxSoFar): if not node: return 0; count = 1 if node.val >= maxSoFar else 0; newMax = max(maxSoFar, node.val); return count + dfs(node.left, newMax) + dfs(node.right, newMax); return dfs(root, float('-inf')). Clean, readable, and O(n) time.

Preorder DFS — process current node before children — is the natural fit here because we need the maximum from root to the current node before we can classify the current node as good or not. We cannot determine this after visiting children because the children do not know the path above their parent.

In contrast, postorder DFS (process children before current) is used when the current node's result depends on what the children return — like in Max Path Sum or LCA. Here the dependency is reversed: children depend on what the parent passes down. The direction of dependency dictates the traversal order.

This distinction is fundamental to understanding tree recursion. When a node needs information from its ancestors, pass it down as parameters (preorder). When a node's result depends on its descendants, return it upward (postorder). Count Good Nodes is a textbook example of the preorder downward-passing pattern.

An iterative approach uses a queue of (node, maxSoFar) pairs. Start by enqueuing (root, float('-inf')). At each step, dequeue a pair, check if the node is good, compute newMax, and enqueue the non-null children with newMax as their maxSoFar. Maintain a running count of good nodes found.

BFS processes the tree level by level rather than depth-first, but the counting logic is identical — each node is still compared against the maximum seen on its path from the root. The maxSoFar value stored alongside each node in the queue serves the same purpose as the parameter in the recursive version.

The iterative BFS approach runs in O(n) time and O(n) space, same as DFS. It avoids potential stack overflow on very deep trees but uses more explicit bookkeeping. For this problem, the recursive DFS is generally preferred in interviews for its clarity and brevity.

Python recursive DFS: class Solution: def goodNodes(self, root): def dfs(node, mx): if not node: return 0; good = 1 if node.val >= mx else 0; mx = max(mx, node.val); return good + dfs(node.left, mx) + dfs(node.right, mx); return dfs(root, float('-inf')). Time O(n), space O(h) for the recursion stack where h is tree height.

Python BFS version using deque: from collections import deque; q = deque([(root, float('-inf'))]); count = 0; while q: node, mx = q.popleft(); if node.val >= mx: count += 1; nmx = max(mx, node.val); if node.left: q.append((node.left, nmx)); if node.right: q.append((node.right, nmx)); return count. Both solutions pass all test cases and handle negative values correctly.

Java solution: public int goodNodes(TreeNode root) { return dfs(root, Integer.MIN_VALUE); } private int dfs(TreeNode node, int max) { if (node == null) return 0; int count = node.val >= max ? 1 : 0; int newMax = Math.max(max, node.val); return count + dfs(node.left, newMax) + dfs(node.right, newMax); }. Uses Integer.MIN_VALUE as the initial max so the root is always counted.

Binary Tree Maximum Path Sum (LeetCode 124) uses postorder DFS where each node combines left and right subtree results — the opposite information-flow direction from Count Good Nodes. Studying both problems back to back sharpens intuition for when to pass information down versus bubble it up.

Lowest Common Ancestor (LeetCode 236) is another postorder problem where the result depends on what both subtrees return. Path Sum II (LeetCode 113) and Path Sum III (LeetCode 437) are preorder problems like Count Good Nodes — they also track accumulated path information from root to current node via parameters.

Flatten Binary Tree to Linked List (LeetCode 114) and tree serialization problems belong to the preorder family as well. Recognizing the pass-downward pattern — where a parameter accumulates state along the path — is the unifying skill across this entire family of tree DFS problems.