LeetCode 1448 · Medium · Trees

Count Good Nodes in Binary Tree

A node is good when no node on the path from the root down to it has a bigger value. Count the good nodes of a binary tree.

O(n)time
O(h)space · call stack
DFScarry the path max down

level order as on LeetCode, null = no child · 1 to 15 nodes, 4 levels · values −99 to 99

Call stack frames dfs(node, maxVal) shown as node,max · N = null · badges = good nodes in that subtree

public int goodNodes(TreeNode root) { return dfs(root, root.val);}private int dfs(TreeNode node, int maxVal) { if (node == null) { return 0; } int res = node.val >= maxVal ? 1 : 0; maxVal = Math.max(maxVal, node.val); res += dfs(node.left, maxVal); res += dfs(node.right, maxVal); return res;}
node
—
maxVal
—
res
—
good so far
0

Why it works

  1. Brute force walks back up from every node to the root, checking each ancestor: O(n·h), which is O(n²) on a chain.
  2. Only one number about the path matters: its maximum. Pass it down as an argument. A node is good when node.val >= maxVal, and its children inherit max(maxVal, node.val).
  3. One visit per node, O(1) work each: O(n) time. The path max lives in the call frames, so the stack is the only extra space: O(h).
  4. Pitfall: using > instead of >=. A node equal to the path max is still good (Ex 2's second 3 counts). A tie only helps when nothing bigger sits higher: in the negatives preset, the −9 under −9 is not good because −5 is above both.
  5. Pattern: state flows down as arguments, counts flow up as return values. Validate BST (98) passes bounds down the same way.