Count Good Nodes in Binary Tree

Problem

A node is "good" if no node on the path from the root to it has a strictly greater value. Return the number of good nodes.

Constraints

• 1 ≤ nodes ≤ 10⁵

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def goodNodes(self, root):
        def dfs(node, mx):
            if not node:
                return 0
            good = 1 if node.val >= mx else 0
            mx = max(mx, node.val)
            return good + dfs(node.left, mx) + dfs(node.right, mx)
        return dfs(root, float('-inf'))

Java

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }
    private int dfs(TreeNode n, int max) {
        if (n == null) return 0;
        int count = (n.val >= max) ? 1 : 0;
        int next = Math.max(max, n.val);
        return count + dfs(n.left, next) + dfs(n.right, next);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.