#1448 - Count Good Nodes in Binary Tree

MediumBinary Tree - DFS

Given the root of a binary tree, a node X is 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.

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

Solution Space

Try it

/**
 * Counts "good" nodes — nodes whose value is >= all ancestors.
 *
 * @param root Root of the binary tree
 * @returns Number of good nodes
 */
export function goodNodes(root: TreeNode | null): number {
  return dfs(root, -Infinity);
}

function dfs(node: TreeNode | null, maxSoFar: number): number {
  if (!node) return 0;

  const isGood = node.val >= maxSoFar ? 1 : 0;
  const newMax = Math.max(maxSoFar, node.val);

  return isGood + dfs(node.left, newMax) + dfs(node.right, newMax);
}

Approach: DFS with running max – pass the maximum value from root to current node; count the node if it meets or exceeds that max.

Time: O(n) – visits every node once.

Space: O(h) – recursion stack depth.

#1372 Longest ZigZag Path in a Binary Tree

#199 Binary Tree Right Side View