Count Good Nodes In Binary Tree

Whether a node is “good” depends only on the maximum value seen so far along the path from the root — that value can simply be carried down as an extra DFS argument, so each node is checked in O(1) without ever re-walking a path.

Brute Force (re-walk each path)

Time O(n^2)Space O(h)

For every node, walk back up to the root (or, equivalently, track the full path down and re-scan it) to check whether any ancestor has a strictly greater value.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def count(node: TreeNode | None, path: list[int]) -> int:
            if node is None:
                return 0
            is_good = 1 if node.val >= max(path, default=node.val) else 0
            new_path = path + [node.val]
            return is_good + count(node.left, new_path) + count(node.right, new_path)

        return count(root, [])

Complexity: max(path) re-scans the whole path-so-far at every node, and paths can be O(n) long → O(n^2) time worst case (a skewed tree). Space for the path list plus recursion stack → O(h).

DFS Carrying Running Max

OptimalTime O(n)Space O(h)

Pass the maximum value seen so far as a single running argument instead of the whole path. A node is good exactly when its value is at least that running max; the max passed to its children is then max(running_max, node.val).

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node: TreeNode | None, max_so_far: int) -> int:
            if node is None:
                return 0
            is_good = 1 if node.val >= max_so_far else 0
            new_max = max(max_so_far, node.val)
            return is_good + dfs(node.left, new_max) + dfs(node.right, new_max)

        return dfs(root, root.val)

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

1 / 5

seenresultdiscarded

Root 3 starts with max_so_far=3. 3 >= 3, so it is good. Pass max_so_far=3 down.

Complexity: each node does O(1) work with the running max instead of rescanning a path → O(n) time. Space is the recursion stack (the running max is a single O(1) value passed along it) → O(h).