Count Good Nodes 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

A node X is good if there are no nodes with a value greater than X on the path from root to X. The root is always good.

#       3
#      / \
#     1   4
#    /   / \
#   3   1   5

# Node 3 (root): good (root is always good)
# Node 1: NOT good (3 > 1 on path)
# Node 4: good (3 ≤ 4 on path)
# Node 3 (left leaf): good (3 ≤ 3 on path)
# Node 1 (right): NOT good (3,4 > 1)
# Node 5: good (3,4 ≤ 5)
# Answer: 4 good nodes

DFS approach — track the maximum value seen so far on the path:

Pass max_so_far as you traverse down
If current node's value ≥ max_so_far → it's good, increment count
Update max_so_far = max(max_so_far, node.val) for children
Recurse on left and right subtrees

📋 Instructions

Implement `good_nodes(root)` using DFS. Test with the tree above.

DFS helper with (node, max_val). If node is None, return 0. good = 1 if node.val >= max_val else 0. new_max = max(max_val, node.val). Return good + dfs(left, new_max) + dfs(right, new_max).

🧪 Test Cases

Input

good_nodes(root)

Expected

4

Test case 1

Input

good_nodes(TreeNode(1))

Expected

1

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›