Count Good Nodes in Binary Tree

MediumTreesTreeDFSBFSBinary Tree

Problem

Given a binary tree, call a node "good" if no node on the path from the root down to it has a strictly greater value. The root is always good, since it has no ancestors. Count how many nodes qualify.

Example. For a tree with root 3, left child 1, and right child 4 (whose own left child is 5), the good nodes are 3, 4, and 5: three good nodes out of four total, since 1 is beaten by the root.

Key idea

Without a way to look upward, the naive approach re-derives each node's full ancestor path from scratch, repeating work across nearby nodes. The fix is to carry "the largest ancestor value so far" down through the recursion instead of recomputing it.

Do a single top-down traversal, passing the maximum value seen from the root to the current node's parent. At each node, compare its own value to that running maximum: if it is at least as large, the node is good, and the maximum passed to its children becomes this node's value; otherwise the maximum stays unchanged. One pass, carrying one extra number, replaces re-walking ancestor chains for every node.

Solution

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

function goodNodes(root: TreeNode | null): number {
  function dfs(node: TreeNode | null, maxSoFar: number): number {
    if (node === null) {
      return 0;
    }
    const isGood = node.val >= maxSoFar ? 1 : 0;
    // Carry the largest ancestor value down instead of re-walking the path from the root.
    const nextMax = Math.max(maxSoFar, node.val);
    return isGood + dfs(node.left, nextMax) + dfs(node.right, nextMax);
  }

  // Seed with the root's own value, since the root has no ancestors and is always good.
  return root === null ? 0 : dfs(root, root.val);
}

Complexity

  • Time: O(n). Each node is visited once with constant work.
  • Space: O(h). The recursion stack, where h is the tree's height (O(n) worst case for a skewed tree).

Watch out for

  • Use "greater than," not "greater than or equal": equal values along the path keep a node good.
  • Seed the running maximum with the root's own value before recursing into its children.
  • This has nothing to do with binary-search-tree ordering; it works identically on any binary tree.

Pattern

This is a "thread state down the recursion" pattern: pass an accumulated value, here a running maximum, as a parameter instead of recomputing it per node. The same idea drives path-sum problems and range-based validation, such as binary search tree validity with an inherited bound.

Related questions