Count Good Nodes in Binary Tree

Difficulty: Medium

You're given the root of a binary tree. A node is called good if, when you look at the path from the root down to that node, no node along the way has a value greater than the node itself. In other words, the node's value must be greater than or equal to every value that came before it on the way down (its own value counts, so the root is always good).

Count how many good nodes are in the tree.

Examples

Input: root = [3,1,4,3,null,1,5]
Output: 4

The good nodes are the root (3), the 3 under the left 1, the 4, and the 5 — each is at least as large as everything above it on its path.

Input: root = [3,3,null,4,2]
Output: 3

3 (root), 3 (its child), and 4 are good. 2 is not, because 4 appeared earlier on its path.

Input: root = [1]
Output: 1

A single node with no ancestors is trivially good.

Constraints

The number of nodes is in the range [1, 10^5].
Each node's value is between -10^4 and 10^4.

Approach

This is a top-down problem: whether a node is good depends only on its ancestors, not on anything below it. So as you walk down from the root, carry along the maximum value seen so far on the current path. At each node, compare its value to that running maximum — if it's greater than or equal, it's good, and it also becomes the new running maximum for its children.

Solutions

Recursive DFS (Top-Down)

Do a depth-first traversal, passing the maximum value seen so far on the path down to each recursive call. At each node, check if its value is greater than or equal to that maximum — if so, count it as good, and use its value as the new maximum for the children below it.

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

function goodNodes(root) {
  function dfs(node, maxSoFar) {
    if (node === null) return 0;

    let count = 0;
    if (node.val >= maxSoFar) {
      count = 1;
      maxSoFar = node.val;
    }

    return count + dfs(node.left, maxSoFar) + dfs(node.right, maxSoFar);
  }

  return dfs(root, -Infinity);
}

Time: O(n) · Space: O(h) — recursion stack, where h is the tree's height

Optimal — Iterative BFS

The same idea works without recursion by using an explicit queue, where each queue entry carries a node along with the running maximum for the path that led to it. This avoids recursion-depth concerns on very deep, skewed trees.

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

function goodNodes(root) {
  if (root === null) return 0;

  let count = 0;
  const queue = [[root, root.val]];

  while (queue.length > 0) {
    const [node, maxSoFar] = queue.shift();
    if (node.val >= maxSoFar) count++;

    const newMax = Math.max(maxSoFar, node.val);
    if (node.left !== null) queue.push([node.left, newMax]);
    if (node.right !== null) queue.push([node.right, newMax]);
  }

  return count;
}

Time: O(n) · Space: O(n) — the queue can hold an entire level's worth of nodes