Skip to main content

1448 - Count Good Nodes in Binary Tree

Difficulty: Medium | Pattern: Tree DFS | Company tags: Microsoft, Amazon, Facebook

Problem Statement​

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.val.

Return the number of good nodes in the binary tree.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes 3(root), 4, 3, 5 are good.
    3
   / \
  1   4
 /   / \
3   1   5

Example 2:

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

Approach: DFS with Max Tracking — O(n)​

Key insight: DFS from root, tracking the maximum value seen so far on the current path. A node is "good" if its value is >= that maximum.

def goodNodes(root) -> int:
    def dfs(node, max_so_far):
        if not node:
            return 0
        
        count = 1 if node.val >= max_so_far else 0
        new_max = max(max_so_far, node.val)
        
        count += dfs(node.left, new_max)
        count += dfs(node.right, new_max)
        
        return count
    
    return dfs(root, float('-inf'))

Algorithm Flow​

Dry Run​

Tree: [3,1,4,3,null,1,5]

dfs(3, -inf): 3 >= -inf ✓ count=1, max=3
  dfs(1, 3): 1 < 3 ✗ count=0, max=3
    dfs(3, 3): 3 >= 3 ✓ count=1 → returns 1
    dfs(None, 3): 0
    → returns 1
  dfs(4, 3): 4 >= 3 ✓ count=1, max=4
    dfs(1, 4): 1 < 4 ✗ count=0 → returns 0
    dfs(5, 4): 5 >= 4 ✓ count=1 → returns 1
    → returns 0+1+1=2
Total: 1+1+2 = 4

Output: 4 ✓

Iterative BFS Version​

from collections import deque

def goodNodes(root) -> int:
    if not root:
        return 0
    count = 0
    queue = deque([(root, float('-inf'))])
    while queue:
        node, max_so_far = queue.popleft()
        if node.val >= max_so_far:
            count += 1
        new_max = max(max_so_far, node.val)
        if node.left:
            queue.append((node.left, new_max))
        if node.right:
            queue.append((node.right, new_max))
    return count

Edge Cases​

  • Single node → always good (root is always good)
  • All decreasing values down → only root is good
  • All same values → all nodes are good

Complexity​

  • Time: O(n) — visit every node once
  • Space: O(h) — recursion stack; O(log n) balanced, O(n) skewed

Key Terms​

TermDefinition
DFS (Depth-First Search)Traversal strategy that fully explores one branch of the tree before backtracking, used here to walk root-to-leaf paths.
Path maximum trackingCarrying the running maximum value seen along the current root-to-node path as a parameter through recursion.
Good nodeA node whose value is greater than or equal to every ancestor on its path from the root.
Recursion stackThe implicit call stack used by DFS; its depth equals the tree height and determines auxiliary space usage.
Root-to-node pathThe unique sequence of nodes from the root down to a given node in a tree, used as the scope for the "no greater ancestor" condition.

FAQ​

  1. Can this be solved without extra space (excluding recursion)? The DFS approach uses O(1) extra variables per call; the only space cost is the O(h) recursion stack, which is unavoidable for tree traversal unless converted to an iterative approach with an explicit stack, which still costs O(h).

  2. What if the tree is empty? root is None, so dfs returns 0 immediately (or the BFS loop never starts), and the answer is 0 good nodes.

  3. How would this change if we wanted the actual list of good nodes instead of a count? Instead of returning an integer count, append node.val (or the node itself) to a shared list or accumulate results in a return list from each recursive call, merging left and right results plus the current node when it qualifies.

  4. Why pass max_so_far as a parameter instead of using a global/mutable variable? Each root-to-node path has its own independent maximum; passing it by value keeps sibling subtrees isolated so a high value in the left subtree doesn't incorrectly affect the right subtree's evaluation.

  5. Does the initial value need to be float('-inf'), or could it be root.val? Using float('-inf') guarantees the root itself is always counted as good regardless of its value (including negative values), which matches the problem's definition that the root always qualifies.

Quick Revision​

  • Problem: count nodes where no ancestor on the root-to-node path has a strictly greater value.
  • Pattern: single-pass DFS carrying the max value seen so far as a parameter.
  • A node is good if node.val >= max_so_far.
  • Update max_so_far to max(max_so_far, node.val) before recursing into children.
  • Base case: None node contributes 0 to the count.
  • Initialize the top-level call with max_so_far = float('-inf') so the root is always good.
  • Sum counts from left subtree, right subtree, and current node's own contribution.
  • Time complexity O(n) since every node is visited exactly once.
  • Space complexity O(h): O(log n) for balanced trees, O(n) worst case for skewed trees.
  • Iterative BFS variant swaps the call stack for an explicit queue holding (node, max_so_far) pairs.
  • 104-MaximumDepthOfBinaryTree.md — same DFS-with-recursion pattern for computing a value along tree paths.
  • 112-PathSum.md — DFS carrying a running value (remaining sum) down each root-to-leaf path, analogous to carrying max_so_far.
  • 113-PathSumII.md — extends path tracking to collect and return full paths rather than just a count.