Trees crash course ↗ · 146

1448. Count Good Nodes in Binary Tree

A node is good when no larger value exists on the path from the root to that node. The key is to thread a pathMax variable down through the DFS — each node compares itself to that running maximum in O(n) time.

● MediumDFSTree TraversalPreorderTypeScript

PROBLEM What we're solving

Given a binary tree, count nodes that are good: a node X is good if there is no node with a value greater than X.val on the path from the root down to X (the node itself is included in the path).

Concrete example: tree 3,1,4,3,null,1,5 (level-order). The root 3 is trivially good (nothing above it). Its left child 1 is not good because 3 > 1 is on the path. The right child 4 is good (4 ≥ 3). Left grandchild 3 is good (3 ≥ 3). Right subtree of 4: left child 1 is not good (1 < 4), right child 5 is good (5 ≥ 4). Answer: 4.

KEY IDEA Thread the running maximum down the DFS

Insight → a node is good iff its value is ≥ the maximum value seen on the root-to-node path. Thread that maximum as a parameter pathMax through a DFS — each recursive call passes Math.max(pathMax, node.val) to its children. No extra data structure needed; the call stack is the path.

RECIPE Preorder DFS with a threading maximum

0 · Base case. If node is null, return 0 — no node, no contribution.
1 · Check goodness. node.val >= pathMax means this node qualifies; count it as 1, otherwise 0.
2 · Update the max. newMax = Math.max(pathMax, node.val). Pass newMax — not pathMax — to children, so they see the highest value on the extended path.
3 · Recurse both subtrees. Return the sum of the current count plus the counts from left and right. Preorder order (check before recursing) is natural here but any order works since we just sum.
4 · Seed the call. Call dfs(root, -Infinity) so the root is always considered good (every finite value ≥ −∞).

Classic confusion → seeding with 0 instead of -Infinity. If the root has a negative value like -5, seeding with 0would incorrectly mark it as "not good" — the root is always good by definition. Use -Infinity (or Number.MIN_SAFE_INTEGER for languages without infinity) to guarantee the root passes the check.

COST Complexity & alternatives

Store full root-to-node path

O(n) time, O(n) space

Track the path array; compute max per node. Same time, extra space.

Thread pathMax parameter

O(n) time, O(h) space

One DFS pass; stack depth = tree height h (O(log n) balanced, O(n) worst).

Iterative alternative

An explicit stack of { node, pathMax } tuples works identically — useful if the interview asks for an iterative solution or if stack overflow is a concern on very deep trees.

Pattern transfer → threading a parameter down a DFS appears in Path Sum (thread a running sum, check at leaves), Maximum Depth of Binary Tree (thread depth count), Validate BST (thread min/max bounds), and Diameter of Binary Tree (return value bubbles up; thread is implicit via the call stack).

RUN IT DFS threading pathMax — count nodes ≥ max-on-path

level-order:

step 0 / 25

STARTBegin DFS from root. Threading pathMax = -∞ down the tree.

1function goodNodes(root: TreeNode | null): number {
2  function dfs(node: TreeNode | null, pathMax: number): number {
3    if (!node) return 0;
4 
5    const isGood = node.val >= pathMax;
6    const newMax = Math.max(pathMax, node.val);
7 
8    return (isGood ? 1 : 0)
9      + dfs(node.left, newMax)
10      + dfs(node.right, newMax);
11  }
12 
13▶  return dfs(root, -Infinity);
14}

State

null

node

—

pathMax

—

isGood

—

newMax

goodCount

current nodegood node (val ≥ pathMax)not good (val < pathMax)on call stack

slowfast

TYPESCRIPT The solution, annotated

countGoodNodes.ts
function goodNodes(root: TreeNode | null): number {
  function dfs(node: TreeNode | null, pathMax: number): number {
    if (!node) return 0;

    const isGood = node.val >= pathMax;
    const newMax = Math.max(pathMax, node.val);

    return (isGood ? 1 : 0)
      + dfs(node.left, newMax)
      + dfs(node.right, newMax);
  }

  return dfs(root, -Infinity);
}

Reading it block by block

Inner function dfs. Accepts the current node and pathMax — the largest value seen from the root down to (but not including) this node. Nesting it inside goodNodes keeps the interface clean.

Base case. A null node contributes zero good nodes. This naturally handles empty trees and the children of leaf nodes.

Goodness check. Compare node.val to pathMax. Because we seed with -Infinity, the root always passes (any finite number ≥ −∞). The boolean is cast to 1 or 0 via the ternary.

Update and recurse. newMax is the max the children will see. We pass newMax (not the old pathMax) so children correctly know the highest ancestor value on their extended path. The return value is the sum of this node's count plus both subtree counts — no global state needed.

Root call. dfs(root, -Infinity) — -Infinity ensures the root is always good regardless of its value.

Complexity → O(n) time — every node is visited exactly once. O(h) space for the call stack where h is the tree height (O(log n) balanced, O(n) skewed). No auxiliary data structures.

INTERVIEWFollow-ups they'll ask

"Can you do it iteratively?" Yes: push [node, pathMax] tuples onto an explicit stack and process them in a loop — identical logic, no recursion.
"What if we want the actual good nodes, not just the count?" Collect nodes into an array instead of summing integers; same DFS shape.
"What if the tree is very deep / skewed?" Recursive DFS risks stack overflow on a degenerate linked-list tree with n = 10⁵ nodes. The iterative version avoids this.
"What changes for a min-good variant?" Thread pathMin and check node.val <= pathMin; seed with Infinity.
"Validate BST uses the same idea — can you explain the connection?" Both thread bounds down the DFS. Validate BST threads a [min, max] window; this problem threads a single pathMax.

OPTIMAL DFS

countGoodNodes.ts
function goodNodes(root: TreeNode | null): number {
  function dfs(node: TreeNode | null, pathMax: number): number {
    if (!node) return 0;

    const isGood = node.val >= pathMax;
    const newMax = Math.max(pathMax, node.val);

    return (isGood ? 1 : 0)
      + dfs(node.left, newMax)
      + dfs(node.right, newMax);
  }

  return dfs(root, -Infinity);
}

Complexity → O(n) time — every node is visited exactly once. O(h) space for the call stack where h is the tree height (O(log n) balanced, O(n) skewed). No auxiliary data structures.

ALT 1 Brute force — re-collect the root path for every node

O(n²) time · O(n) space

Visit every node, and for each one independently search from the root to gather the values on the path down to it, then mark it good if its value is >= the max of that path. No running maximum is threaded down.

approach-2.ts
function goodNodes(root: TreeNode | null): number {
  // Find the path (values) from root down to 'target'; null if not found.
  function pathTo(node: TreeNode | null, target: TreeNode, acc: number[]): number[] | null {
    if (!node) return null;
    acc.push(node.val);
    if (node === target) return [...acc];
    const left = pathTo(node.left, target, acc);
    if (left) { acc.pop(); return left; }
    const right = pathTo(node.right, target, acc);
    acc.pop();
    return right;
  }

  let good = 0;
  function visit(node: TreeNode | null): void {
    if (!node) return;
    const path = pathTo(root, node, [])!;       // O(n) search per node
    if (node.val >= Math.max(...path)) good++;
    visit(node.left);
    visit(node.right);
  }

  visit(root);
  return good;
}

Note → Each node triggers a fresh O(n) root-to-node search just to recover the path it already sits on, making the whole count O(n²). Threading the running pathMax down the single DFS (the optimal) removes the repeated work for O(n).

MNEMONIC The one-liner

"Pass the high-water mark down — a node is good if it matches or beats the record."

TRIGGERS When you see _ → reach for _

"good node" or path-maximum condition on a tree	DFS threading pathMax
count nodes satisfying a root-to-node property	preorder DFS with parameter
tree + running max/min/sum on path	thread value as DFS argument
validate BST / path sum / count good nodes	pass bounds/accumulator into recursive call

SKELETON The reusable shape

skeleton.ts
function goodNodes(root: TreeNode | null): number {
  function dfs(node: TreeNode | null, pathMax: number): number {
    if (!node) return 0;
    const isGood = node.val >= pathMax;
    const newMax = Math.max(pathMax, node.val);
    return (isGood ? 1 : 0)
      + dfs(node.left, newMax)
      + dfs(node.right, newMax);
  }
  return dfs(root, -Infinity);
}

FLASHCARDS Tap to flip

What makes a node "good"?

Its value is ≥ the maximum value on the root-to-node path (inclusive).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For tree [3,1,4,3,null,1,5] (level-order), what is the count of good nodes?

QUESTION 02

What value should you use to seed pathMax for the initial call?

QUESTION 03

What value do you pass as pathMax to a child node?

QUESTION 04

What is the time complexity of the threading-pathMax DFS solution?

QUESTION 05

What is the space complexity (ignoring output)?

QUESTION 06

A single-node tree with value -7: how many good nodes?

QUESTION 07

Which other tree problem uses the exact same "thread bounds down DFS" pattern?

QUESTION 08

#1448 · Count Good Nodes in Binary TreeDFS threads the running maximum down the path from root to each node; a node is "good" when its value is at least the maximum seen so far on its root-to-node path.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Thread the running maximum down the DFS

RECIPE Preorder DFS with a threading maximum

COST Complexity & alternatives

Iterative alternative

RUN IT DFS threading pathMax — count nodes ≥ max-on-path

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL DFS

ALT 1 Brute force — re-collect the root path for every node

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _