Faangprep Logo
Log inStart free
Browse curriculum

Count Good Nodes in Binary Tree

Count the nodes with no bigger value above them by passing the maximum seen so far down a DFS: one comparison per node.

MediumSolve on LeetCode

Problem Understanding

Count Good Nodes in Binary Tree: a node X is good if the path from the root to X contains no node with a value greater than X. Return the number of good nodes.

Example: [3,1,4,3,null,1,5] returns 4: the root 3, the 3 under the 1, the 4, and the 5.

The Intuition: Carry the Path Maximum Down

Whether a node is good depends only on the largest value above it, not on the whole path. So pass that one number down:

  1. Call dfs(node, maxSoFar), starting with dfs(root, root.val).
  2. The node is good when node.val >= maxSoFar.
  3. Its children receive max(maxSoFar, node.val).

This is the "pass state down" form of depth-first search, the same shape as Path Sum, which passes the remaining sum, and Validate Binary Search Tree, which passes the allowed range.

Interactive Walkthrough

Under each visited node is the path maximum it was compared with. Good nodes turn green and the others red. Try Decreasing to see every node below the root lose to it.

Dry Run Table

Input: [3,1,4,3,null,1,5]

Node Path max above Good? Max passed down
3 (root) 3 yes 3
1 3 no 3
3 (under 1) 3 yes 3
4 3 yes 4
1 (under 4) 4 no 4
5 4 yes 5

Answer: 4.

The Solution Template

A recursive DFS with the path maximum as a parameter. LeetCode guarantees at least one node.

Count Good Nodes in Binary Tree Code
1var goodNodes = function(root) {
2    const dfs = (node, maxSoFar) => {
3        if (!node) return 0;
4        const good = node.val >= maxSoFar ? 1 : 0;
5        maxSoFar = Math.max(maxSoFar, node.val);
6        return good + dfs(node.left, maxSoFar) + dfs(node.right, maxSoFar);
7    };
8    return dfs(root, root.val);
9};

Edge Cases & Common Mistakes

  • Equal values: >=, not >: a node equal to the path maximum is still good.
  • The root: start with maxSoFar = root.val (or negative infinity) so the root counts.
  • Comparing with the parent only: a node can be bigger than its parent but smaller than a grandparent; carry the maximum of the whole path.
  • Updating the maximum before the check: compare first, then raise the maximum for the children.
  • Deep, skewed trees: recursion depth equals the height; an explicit stack avoids overflow on very deep inputs.

Summary

DFS with the path maximum as a parameter: count the node if node.val >= maxSoFar, then pass max(maxSoFar, node.val) to both children. O(n) time and O(h) space for the recursion.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Path Sum II

Next

Longest Univalue Path

The approach, step by step

  1. Start at the root

    Call dfs(root, root.val), so the root compares with itself and counts as good.

  2. Check and pass the maximum down

    At each node, add 1 if node.val >= maxSoFar. Call both children with max(maxSoFar, node.val).

  3. Sum the counts

    An empty child returns 0; each node returns its own 0 or 1 plus both children's counts.

Frequently asked questions

What is a good node in a binary tree?

A node X is good if no node on the path from the root to X has a value greater than X. Equal values are allowed, and the root is always good because its path contains only itself.

How do you count good nodes efficiently?

Run a DFS that carries the largest value seen on the path so far. At each node, it is good if node.val >= maxSoFar. Then pass max(maxSoFar, node.val) to both children. Every node is visited once, so the time is O(n).

Can BFS solve Count Good Nodes too?

Yes. Store each node in the queue together with its path maximum. The check is the same; only the visiting order changes. DFS is shorter because the path maximum travels naturally as a parameter.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description