← all entries
A-055● Day 552026.07.01mediumleetcode #1448neetcode150

Count Good Nodes in Binary Tree

#tree#depth-first-search#breadth-first-search#binary-tree
↗ leetcode #1448 · count-good-nodes-in-binary-tree
01

Problem

· problem
P.055

Count Good Nodes in Binary Tree

↗ leetcode #1448

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. Return the number of good nodes in the binary tree.

constraints
  • · 1 ≤ number of nodes ≤ 10^5
  • · -10^4 ≤ node value ≤ 10^4
// paraphrased summary — see source for full text
examples
example 1input → output
[3,1,4,3,null,1,5]
4
example 2input → output
[3,3,null,4,2]
3
example 3input → output
[1]
1
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Is the root node always considered a good node?
  • ☐
    Can node values be negative?
  • ☐
    Does the path from root to node X include the node X itself?
  • ☐
    If all nodes have the same value, are they all good nodes?
  • ☐
    Must the path always start from the root?
  • ☐
    Do we need to handle the case when the tree is empty?
  • ☐
    Can we modify the tree structure?
  • ☐
    Do we need to return the good nodes themselves?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Base Case: Check if Node Exists
○
if not node:
○
if node is None:
○
if node == None:
step 2· Check if Current Node is Good│ nested
○
res = 1 if node.val >= maxVal else 0
○
res = 1 if node.val > maxVal else 0
○
res = 1 if node.val <= maxVal else 0
step 3· Update Maximum Value on Path│ nested
○
maxVal = max(maxVal, node.val)
○
maxVal = node.val
○
maxVal = min(maxVal, node.val)
step 4· Traverse Left Subtree and Accumulate Count│ nested
○
res += dfs(node.left, maxVal)
○
res += dfs(node.left, node.val)
○
dfs(node.left, maxVal)
step 5· Traverse Right Subtree and Accumulate Count│ nested
○
res += dfs(node.right, maxVal)
○
res = dfs(node.right, maxVal)
○
res += dfs(node.right, node.val)
step 6· Return Accumulated Count│ nested
○
return res
○
return 1
○
return res + 1
step 7· Initial Call: Start DFS from Root
○
return dfs(root, root.val)
○
return dfs(root, float('-inf'))
○
return dfs(root, 0)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def goodNodes(self, root: TreeNode) -> int:
9
        def dfs(node, maxVal):
10
            if not node:
11
                return 0
12
13
            res = 1 if node.val >= maxVal else 0
14
            maxVal = max(maxVal, node.val)
15
            res += dfs(node.left, maxVal)
16
            res += dfs(node.right, maxVal)
17
            return res
18
19
        return dfs(root, root.val)
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[3,1,4,3,null,1,5]
→
4
case 2
[3,3,null,4,2]
→
3
case 3
[1]
→
1
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.