Count Good Nodes in Binary Tree

MediumTree DFSNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

You're given the root of a binary tree. A node is good if no node on the path from the root down to it has a larger value. Return the number of good nodes. The root is always good.

Examples

root = [4,2,6,5,null,1,7] returns 4

4, 6, and 7 are each the largest on their paths. 5 sits below 4 and 2, both no larger, so it is good too. 2 and 1 each have a larger ancestor.

root = [2,2,2] returns 3

An equal value does not disqualify a node, so all three are good.

root = [9] returns 1

The root alone is good.

Constraints

1 <= number of nodes <= 10^5
-10^4 <= Node.val <= 10^4

Hints

Hint 1

Whether a node is good depends only on the values above it on its path. What single number summarizes that path?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Carry the largest value seen on the path so far down a DFS. At each node, it is good when node.val >= maxSoFar; count it, then visit both children with max(maxSoFar, node.val). Start at the root with its own value. The solutions use an explicit stack of (node, max) pairs, so a deep, skewed tree can't overflow the call stack. Each node is visited once: O(n) time, O(h) space.

Time

O(n)

Space

O(h)

Pitfall

Comparing only with the parent. A node can be larger than its parent and still smaller than an ancestor higher up, like 1 under 6 in a path that started at 4.

Solutions

class Solution {
    public int goodNodes(TreeNode root) {
        int count = 0;
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> maxes = new ArrayDeque<>();
        nodes.push(root);
        maxes.push(root.val);
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int maxSoFar = maxes.pop();
            if (node.val >= maxSoFar) count++;
            int next = Math.max(maxSoFar, node.val);
            if (node.left != null) {
                nodes.push(node.left);
                maxes.push(next);
            }
            if (node.right != null) {
                nodes.push(node.right);
                maxes.push(next);
            }
        }
        return count;
    }
}

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        count = 0
        stack = [(root, root.val)]
        while stack:
            node, max_so_far = stack.pop()
            if node.val >= max_so_far:
                count += 1
            next_max = max(max_so_far, node.val)
            if node.left:
                stack.append((node.left, next_max))
            if node.right:
                stack.append((node.right, next_max))
        return count