AlgoMaster Logo

Count Good Nodes in Binary Tree

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to traverse a binary tree and count every node whose value is greater than or equal to all the values on the path from the root down to that node. Equivalently, a node is "good" if it holds the maximum value (or ties for it) along its root-to-node path.

The root is always good since it has no ancestors to compete with. Every other node needs a check against its ancestors: if no ancestor has a strictly greater value, the node is good.

The check depends on the ancestors in only one way: their maximum value. If the current node's value is at least that maximum, the node is good, regardless of how long the path is or what the other values are. This reduces the problem to a single traversal that carries one number downward.

Key Constraints:

  • 1 <= number of nodes <= 10^5 → We need an O(n) solution. Anything that reprocesses the path from scratch at every node risks O(n * h) or O(n^2) on skewed trees, which could time out.
  • -10^4 <= Node.val <= 10^4 → Values can be negative. A root with value -5 is still good (it is the max on its own path). Do not assume values are positive.
  • At least 1 node → No need to handle an empty tree.

Approach 1: DFS Storing the Full Path

Intuition

Implement the definition directly: for every node, look at the entire path from root to that node and check whether the node has the largest value (or ties for it). Maintain a list holding the values on the current path, push a node's value when entering it, scan the list for the maximum, and pop when backtracking.

This is correct and easy to reason about, but it repeats work. Between a parent and its child the path changes by one element, yet every visit rescans the whole list to recompute the maximum, which costs O(h) per node instead of O(1).

Algorithm

  1. Start a DFS from the root with an empty path list.
  2. At each node, append the node's value to the path list.
  3. Scan the path list to find the maximum value.
  4. If the current node's value is greater than or equal to that maximum, it is a good node. Increment the count.
  5. Recurse into the left and right children.
  6. After both recursive calls return, remove the last element from the path list (backtrack).
  7. Return the total count of good nodes.

Visualization and Code

Loading animation...

The next approach removes both the path list and the scan by carrying the maximum forward as a single value.

Approach 2: DFS with Max Tracking (Recursive)

Intuition

The path list in Approach 1 stores more than the check needs. The goodness test reads one fact from it, the maximum, and that fact can be maintained incrementally: when the traversal moves from a parent to a child, the maximum for the child's path is the larger of the parent's path maximum and the parent's value. That is one comparison per step instead of a scan.

So pass a maxSoFar parameter through the recursion. At each node, the node is good when node.val >= maxSoFar. Then recurse into both children with max(maxSoFar, node.val). Because maxSoFar is passed by value (not by reference), the left and right subtrees each receive their own copy, so a large value found deep in the left subtree cannot affect the check in the right subtree. The backtracking that Approach 1 did with an explicit pop happens here through the call stack alone.

Algorithm

  1. Start DFS from the root with maxSoFar initialized to a sentinel smaller than any node value, such as negative infinity or the minimum integer, so the root always passes the check.
  2. At the current node, count 1 if node.val >= maxSoFar, otherwise 0.
  3. Compute the updated maximum: newMax = max(maxSoFar, node.val).
  4. Recurse into the left child, passing newMax.
  5. Recurse into the right child, passing newMax.
  6. Return the total count from both subtrees plus the current node's contribution.

Visualization and Code

Loading animation...

The recursive DFS is optimal in time but stores its state on the call stack. With up to 10^5 nodes, a skewed tree drives the recursion 10^5 levels deep, enough to overflow the default stack in several runtimes. An iterative traversal keeps the same per-node state in an explicit queue instead.

Approach 3: BFS with Max Tracking (Iterative)

Intuition

This approach applies the same max-tracking idea with an explicit queue instead of the call stack. The queue stores (node, maxSoFar) pairs. When we dequeue a pair, we check whether the node is good, compute the updated maximum, and enqueue its children with that value. Each node enters the queue exactly once, already paired with the maximum along its own root path, so subtrees cannot interfere with each other. The traversal order changes from depth-first to level-by-level, which does not matter here because the check at each node uses only path information, never information from siblings.

Algorithm

  1. Initialize a queue with the pair (root, sentinel), where the sentinel is smaller than any node value.
  2. Initialize a count variable to 0.
  3. While the queue is not empty:
    • Dequeue a (node, maxSoFar) pair.
    • If node.val >= maxSoFar, increment count.
    • Compute newMax = max(maxSoFar, node.val).
    • If the node has a left child, enqueue (left child, newMax).
    • If the node has a right child, enqueue (right child, newMax).
  4. Return count.

Visualization and Code

Loading animation...