1448. Count Good Nodes in Binary Tree

At a Glance

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

Problem (one-liner)

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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