DSA Tracker

Visualize

Count Good Nodes in Binary Tree

Top-down DFS carrying the path maximum

time O(n)space O(h) recursion stack

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.

Details

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.

Problem:Count Good Nodes in Binary TreeMedium

Top-down DFS carrying the path maximum

step 1 / 10

3
1
3
✓
1
4
5

Call stack

good(3, max=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

Every step in words

Show all 10 steps
  1. 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.
  2. Enter 1 with ceiling 3 (the largest value seen from the root so far). 1 < 3: an ancestor is larger, so it is NOT good. The ceiling stays 3 for its children.
  3. Leaf 3 reached with ceiling 3. 3 >= 3, so nothing above it on the path is larger: it is good, and the ceiling handed to its children rises to 3. This frame returns 1 + 0 + 0 = 1 and pops off the stack.
  4. Both subtrees of 1 are done: left returned 1, right returned 0. This frame returns 0 + 1 + 0 = 1 and pops off the stack.
  5. Enter 4 with ceiling 3 (the largest value seen from the root so far). 4 >= 3, so nothing above it on the path is larger: it is good, and the ceiling handed to its children rises to 4.
  6. Leaf 1 reached with ceiling 4. 1 < 4: an ancestor is larger, so it is NOT good. The ceiling stays 4 for its children. This frame returns 0 + 0 + 0 = 0 and pops off the stack.
  7. Leaf 5 reached with ceiling 4. 5 >= 4, so nothing above it on the path is larger: it is good, and the ceiling handed to its children rises to 5. This frame returns 1 + 0 + 0 = 1 and pops off the stack.
  8. Both subtrees of 4 are done: left returned 0, right returned 1. This frame returns 1 + 0 + 1 = 2 and pops off the stack.
  9. Both subtrees of 3 are done: left returned 1, right returned 2. This frame returns 1 + 1 + 2 = 4 and pops off the stack.
  10. The root's frame returns 4: that is the number of good nodes. Every ✓ badge is a node no ancestor beats; every ✗ had a larger value somewhere above it.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Good Nodes in Binary Tree in the editorAll Binary Trees problemsBack to roadmap