Pattern visualizer

Count Good Nodes in Binary Tree

A node does not need its whole ancestry, only the single largest value on the way down from the root. So carry that ceiling as a parameter: if the node's value is at least the ceiling it is good, and the ceiling for its children becomes its own value. Each frame counts itself (0 or 1) plus whatever its two subtrees return, and the total climbs back up the call stack. The comparison is >= on purpose — an equal ancestor is not greater, so the node still counts. Animated on: root = [3, 1, 4, 3, null, 1, 5] — count the nodes X whose root-to-X path contains no value greater than X. Expected answer: 4..

Top-down DFS carrying the path maximum

time O(n)space O(h) recursion stackstep 1 / 10

✓

Call stack

good(3, max=3)

line 3

Enter 3 with ceiling 3 (the largest value seen from the root so far). 3 >= 3, so nothing above it on the path is larger: it is good, and the ceiling handed to its children rises to 3.

Pseudocode

1FUNCTION good(node, maxSoFar):
2  IF node = null: RETURN 0
3  isGood <- node.val >= maxSoFar
4  ceiling <- MAX(maxSoFar, node.val)
5  count <- 1 IF isGood ELSE 0
6  RETURN count + good(node.left, ceiling) + good(node.right, ceiling)
7answer <- good(root, root.val)

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap