Count Good Nodes In Binary Tree

MEDIUM✓ CHIP-TIMEDLC #1448 — FULL STATEMENT ↗

The drill: Count the nodes that are the biggest value seen anywhere on their own root-to-node path — ties count too, only a strictly bigger ancestor disqualifies you.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and each node needs to be judged by everything sitting above it. Walking from the root down to any single node traces a path, and that node is "good" exactly when its own value is at least as large as every value that appeared earlier on that path.

Ties work in the node's favor — matching the running maximum still counts as good, and only a strictly larger ancestor knocks a node out. The root itself always qualifies, since no ancestor exists above it to beat.

The task is to tally how many nodes across the whole tree earn that label and hand back the single count.

EX 01

root = []

→ 0

EMPTY TREE

EX 02

root = [1]

→ 1

SINGLE NODE

EX 03

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

→ 4

MIXED ANCESTRY

tree sizes range from a single node up to a few thousand
node values can be negative, zero, or positive
ties with the running maximum count as good
only strictly larger ancestors disqualify a node
the root is always good by default

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Each node's status depends only on the values strictly above it — the one number worth carrying downward is the running maximum of the path so far.

HINT 2 THE STRUCTURE

The root is always good, trivially — nothing has beaten it yet. What single number do you need to hand each child before recursing?

HINT 3 ONE STEP FROM THE ANSWER

DFS(node, pathMax): count 1 if node.val >= pathMax, then recurse into both children with max(pathMax, node.val).

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE RUNNING MAXPATTERN · CARRY THE RUNNING MAXroot = [3, 1, 4, 3, null, 1, 5]

STEP 1

Carry the running max of the path from the root downward — a node is good when it ties or beats every ancestor above it.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/count-good-nodes-in-binary-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node: Optional[TreeNode], path_max: float) -> int:
            if not node:
                return 0
            count = 1 if node.val >= path_max else 0
            new_max = max(path_max, node.val)
            return count + dfs(node.left, new_max) + dfs(node.right, new_max)

        return dfs(root, float("-inf"))

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 10 LN

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        if not root:
            return 0

        nodes: List[TreeNode] = []

        def collect(node: Optional[TreeNode]) -> None:
            if not node:
                return
            nodes.append(node)
            collect(node.left)
            collect(node.right)

        collect(root)

        def find_path(node: Optional[TreeNode], target: TreeNode, path: List[int]):
            if not node:
                return None
            path.append(node.val)
            if node is target:
                return list(path)
            left = find_path(node.left, target, path)
            if left is not None:
                return left
            right = find_path(node.right, target, path)
            if right is not None:
                return right
            path.pop()
            return None

        count = 0
        for n in nodes:
            path = find_path(root, n, [])
            ancestor_max = max(path[:-1]) if path[:-1] else float("-inf")
            if n.val >= ancestor_max:
                count += 1
        return count

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 38 LN

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Long.MIN_VALUE);
    }

    private int dfs(TreeNode node, long pathMax) {
        if (node == null) {
            return 0;
        }
        int count = node.val >= pathMax ? 1 : 0;
        long newMax = Math.max(pathMax, node.val);
        return count + dfs(node.left, newMax) + dfs(node.right, newMax);
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 14 LN

class Solution {
    public int goodNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        List<TreeNode> nodes = new ArrayList<>();
        collect(root, nodes);

        int count = 0;
        for (TreeNode n : nodes) {
            List<Integer> path = new ArrayList<>();
            findPath(root, n, path);
            long ancestorMax = Long.MIN_VALUE;
            for (int i = 0; i < path.size() - 1; i++) {
                ancestorMax = Math.max(ancestorMax, path.get(i));
            }
            if (n.val >= ancestorMax) {
                count++;
            }
        }
        return count;
    }

    private void collect(TreeNode node, List<TreeNode> nodes) {
        if (node == null) {
            return;
        }
        nodes.add(node);
        collect(node.left, nodes);
        collect(node.right, nodes);
    }

    private boolean findPath(TreeNode node, TreeNode target, List<Integer> path) {
        if (node == null) {
            return false;
        }
        path.add(node.val);
        if (node == target) {
            return true;
        }
        if (findPath(node.left, target, path) || findPath(node.right, target, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 47 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED