#1448 Count Good Nodes in Binary Tree

frequently reported atMicrosoft Amazon Google

the problem

In plain words

Call a node good if no node on the path from the root down to it has a bigger value. Count the good nodes. The root is always good.

in root = [3,1,4,3,null,1,5]

out 4

The root 3, then 4, 5 and the lower 3 are good; the two 1s are not.

in root = [3,3,null,4,2]

out 3

2 is not good: a 3 sits above it.

in root = [1]

out 1

1 ≤ number of nodes ≤ 10⁵
-10⁴ ≤ Node.val ≤ 10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (top-down)

A node needs only one fact about everything above it: the biggest value so far. Pass that max down as a parameter, and add up the good counts on the way back up.

solutions

From brute force to optimal

Keep the root-to-node path in a list; at every node, scan the list for a bigger value.

Good if no value in path is bigger than node.val.
path.add(node.val), recurse into both children, path.remove(last).

timeO(n·h)

Each node scans up to h ancestors: O(n log n) when balanced, O(n²) for a chain.

spaceO(h)

The path list and the recursion stack.

javajava.util.*

1class Solution {2    public int goodNodes(TreeNode root) {3        return count(root, new ArrayList<>());4    }5 6    /** path holds the values from the root down to node's parent. */7    private int count(TreeNode node, List<Integer> path) {8        if (node == null) return 0;9        boolean good = true;10        for (int above : path) {                        // re-check every ancestor, every time11            if (above > node.val) { good = false; break; }12        }13        path.add(node.val);14        int total = (good ? 1 : 0) + count(node.left, path) + count(node.right, path);15        path.remove(path.size() - 1);16        return total;17    }18}

count(node, maxAbove) = good nodes in this subtree, given the largest value above it.

null → 0.
good = node.val >= maxAbove ? 1 : 0.
max = Math.max(maxAbove, node.val).
Return good + count(left, max) + count(right, max). Start with Integer.MIN_VALUE.

timeO(n)

One visit per node, O(1) work each.

spaceO(h)

Recursion stack: O(log n) when balanced, up to O(n) for a skewed tree.

javajava.util.*

1class Solution {2    public int goodNodes(TreeNode root) {3        return count(root, Integer.MIN_VALUE);           // nothing is above the root4    }5 6    /** Good nodes in this subtree, given the largest value on the path above it. */7    private int count(TreeNode node, int maxAbove) {8        if (node == null) return 0;9        int good = node.val >= maxAbove ? 1 : 0;         // nothing above is bigger10        int max = Math.max(maxAbove, node.val);          // the max my children will see11        return good + count(node.left, max) + count(node.right, max);12    }13}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int goodNodes(TreeNode root) {3        return count(root, Integer.MIN_VALUE);           // nothing is above the root4    }5 6    /** Good nodes in this subtree, given the largest value on the path above it. */7    private int count(TreeNode node, int maxAbove) {8        if (node == null) return 0;9        int good = node.val >= maxAbove ? 1 : 0;         // nothing above is bigger10        int max = Math.max(maxAbove, node.val);          // the max my children will see11        return good + count(node.left, max) + count(node.right, max);12    }13}

The same state, carried on an explicit ArrayDeque instead of the call stack.

Push (root, MIN_VALUE).
Pop; count it if node.val >= max.
Push each child with Math.max(max, node.val).

timeO(n)

Each node is pushed and popped once.

spaceO(h)

At most one waiting sibling per level — on the heap, so a 10⁵-deep chain is safe.

javajava.util.*

1class Solution {2    public int goodNodes(TreeNode root) {3        if (root == null) return 0;4        Deque<TreeNode> nodes = new ArrayDeque<>();5        Deque<Integer> maxAbove = new ArrayDeque<>();   // the largest value above the node at the same position6        nodes.push(root);7        maxAbove.push(Integer.MIN_VALUE);8        int good = 0;9        while (!nodes.isEmpty()) {10            TreeNode node = nodes.pop();11            int max = maxAbove.pop();12            if (node.val >= max) good++;13            int next = Math.max(max, node.val);14            if (node.left != null) { nodes.push(node.left); maxAbove.push(next); }15            if (node.right != null) { nodes.push(node.right); maxAbove.push(next); }16        }17        return good;18    }19}

in the room

How to say it in the interview

talk track

Name the state: "each node only needs the max value on the path above it."
Pass it down as a parameter; return the count up. The root starts with Integer.MIN_VALUE (or its own value).
n can be 10⁵: mention that a chain that deep needs the iterative version in Java.

traps

Comparing only with the parent: in [1,10000,null,5,null,9999], 9999 beats its parent 5 but not the 10000 above it.
Using > instead of >=: a node equal to the max so far is still good.
Starting the max at 0: with negative values the root would wrongly count as bad. Start at Integer.MIN_VALUE.

what they ask next

Follow-ups

Return the good nodes, not just how many?

The same walk; add the node to a list whenever it is good.

Largest difference between a node and one of its ancestors (LC 1026)?

Pass both the min and the max seen so far down the path; at each node the best difference uses one of the two.

before you submit

Edge cases to test

One node → 1.
Ties count: [5,5,5] → 3.
A decreasing chain → only the root is good; an increasing chain → every node is good.

practise next