1448. Count Good Nodes in Binary Tree

Quick Identifier

• Topic: trees
• Pattern: Tree DFS (path max so far)
• Difficulty: Medium
• Companies: Amazon, Google, Microsoft, Meta, Adobe
• Frequency: Medium
• LeetCode: 1448

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(h) from the optimal approach.
• Core Mechanism: Given the root of a binary tree, a node is good if on the path from the root to that node there is no value greater than the node’s value. Return how many good nodes exist.

Concept Explanation

Given the root of a binary tree, a node is good if on the path from the root to that node there is no value greater than the node’s value. Return how many good nodes exist.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• "Good nodes" with root-to-node path comparison
• Track running maximum (or “none larger before”) along the path
• DFS with extra state carried down

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — for each node, walk up to root collecting max — O(n²).
• Better — O(n) single DFS passing maxSoFar — O(h) stack.
• Optimal — same as better — O(n) time / O(h) space — one pass; count when node.Val >= maxSoFar, recurse with updated max.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func goodNodes(root *TreeNode) int {
	count := 0
	var walk func(*TreeNode, int)
	walk = func(node *TreeNode, maxSoFar int) {
		if node == nil {
			return
		}
		if node.Val >= maxSoFar {
			count++
		}
		nextMax := maxSoFar
		if node.Val > maxSoFar {
			nextMax = node.Val
		}
		walk(node.Left, nextMax)
		walk(node.Right, nextMax)
	}
	walk(root, root.Val)
	return count
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function goodNodes(root) {
	let count = 0;
	function walk(node, maxSoFar) {
		if (node === null) {
			return;
		}
		if (node.val >= maxSoFar) {
			count++;
		}
		const nextMax = Math.max(maxSoFar, node.val);
		walk(node.left, nextMax);
		walk(node.right, nextMax);
	}
	walk(root, root.val);
	return count;
}

Walkthrough

Tree: 3 / 1,4 / 3,null,1,5

Count good nodes (depends exact shape—illustrates invariant).

Invariant: maxSoFar is the largest value on the unique root→current path excluding deeper descendants; updating at each step preserves correctness for children.

Edge Cases

• Single node → always good (1)
• All decreasing along a path → only first node per branch might be good (depends values)
• Negative values allowed — same logic with integer comparison

Pitfalls

• Using > instead of >= (root must count as good per definition >=)
• Resetting max incorrectly between subtrees (max is path-specific, not global subtree max)

Similar Problems

• 104. Maximum Depth of Binary Tree — simpler carried state (depth only).
• 437. Path Sum III — different path aggregation (sums, prefix map).
• 113. Path Sum II — path enumeration with running sum.

Variants

• Count nodes that are strict maxima on the path (> only).
• Good nodes in BST with extra ordering constraint.

Mind-Map Tags

#trees #dfs #path-parameter #running-max #good-node