1448. Count Good Nodes in Binary Tree (Medium)

Problem

Given a binary tree, a node X in the tree is called good if, along the path from root to X, there are no nodes with a value greater than X. Return the number of good nodes.

Example

• root = [3,1,4,3,null,1,5] → 4 (roots 3, 4, 5, and the left subtree’s 3)
• root = [3,3,null,4,2] → 3
• root = [1] → 1

LeetCode 1448 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, for each node, walk up to the root

For every node, walk its ancestor chain to verify the invariant.

Python

def good_nodes(root):
    from collections import deque
    parent = {root: None}              # L1: O(1) init
    q = deque([root])
    while q:
        n = q.popleft()                # L2: O(1) dequeue
        for child in (n.left, n.right):
            if child:
                parent[child] = n      # L3: O(1) record parent
                q.append(child)
    count = 0
    for node in parent:
        is_good = True
        cur, v = parent[node], node.val
        while cur is not None:
            if cur.val > v:            # L4: O(h) ancestor walk per node
                is_good = False
                break
            cur = parent[cur]
        if is_good:
            count += 1
    return count

Swift

final class Solution { func goodNodes(_ root: TreeNode?) -> Int { guard let root else { return 0 }; var nodes = [root], parents: [ObjectIdentifier: TreeNode] = [:], read = 0; while read < nodes.count { let node = nodes[read]; read += 1; if let left = node.left { parents[ObjectIdentifier(left)] = node; nodes.append(left) }; if let right = node.right { parents[ObjectIdentifier(right)] = node; nodes.append(right) } }; return nodes.reduce(0) { total, node in var current: TreeNode? = node; var maximum = Int.min; while let item = current { maximum = max(maximum, item.val); current = parents[ObjectIdentifier(item)] }; return total + (node.val >= maximum ? 1 : 0) } } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L2/L3 (BFS build)	$O(1)$	n	$O(n)$
L4 (ancestor walk)	$O(h)$	n	$O(n · h)$ ← dominates

Each of the n nodes walks up to $O(h)$ ancestors. In a balanced tree this is $O(n log n)$; in a skewed tree it’s $O(n²)$.

Complexity

• Time: $O(n · h)$. Each of n nodes walks up $O(h)$.
• Space: $O(n)$ for the parent map.

Wasteful, we’re re-walking ancestor chains that largely overlap.

Approach 2: DFS carrying running max (optimal)

Walk top-down with the running maximum seen so far on the root-to-current path. A node is good iff node.val >= running_max.

Python

def good_nodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0
        good = 1 if node.val >= max_so_far else 0    # L1: O(1) check
        new_max = max(max_so_far, node.val)           # L2: O(1) update
        return good + dfs(node.left, new_max) + dfs(node.right, new_max)  # L3: recurse
    return dfs(root, float('-inf'))

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function goodNodes(root: TreeNode | null): number {
    function dfs(node: TreeNode | null, maxSoFar: number): number {
        if (!node) return 0;
        const good = node.val >= maxSoFar ? 1 : 0;        // L1: O(1) check
        const newMax = Math.max(maxSoFar, node.val);        // L2: O(1) update
        return good + dfs(node.left, newMax) + dfs(node.right, newMax);  // L3: recurse
    }
    return dfs(root, -Infinity);
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func goodNodes(root *TreeNode) int {
    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, maxSoFar int) int {
        if node == nil {
            return 0
        }
        good := 0
        if node.Val >= maxSoFar {
            good = 1                                       // L1: O(1) check
        }
        newMax := maxSoFar
        if node.Val > newMax {
            newMax = node.Val                              // L2: O(1) update
        }
        return good + dfs(node.Left, newMax) + dfs(node.Right, newMax)  // L3: recurse
    }
    return dfs(root, -1<<31)
}

Swift

final class Solution { func goodNodes(_ root: TreeNode?) -> Int { guard let root else { return 0 }; func count(_ node: TreeNode?, _ maximum: Int) -> Int { guard let node else { return 0 }; return (node.val >= maximum ? 1 : 0) + count(node.left, max(maximum, node.val)) + count(node.right, max(maximum, node.val)) }; return count(root, root.val) } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (good check)	$O(1)$	n	$O(n)$
L2 (update max)	$O(1)$	n	$O(n)$
L3 (recurse both)	$O(1)$ dispatch	n	$O(n)$ ← dominates (all lines tie)

Each node is visited exactly once with $O(1)$ work, carrying the running max as a parameter.

Complexity

• Time: $O(n)$, driven by L3 visiting every node once.
• Space: $O(h)$ recursion.

Pattern: “path-state DFS”

Carry a running invariant (max, min, sum, seen-set) as a parameter. Works for every “a node is X iff the root-to-node path is Y” problem.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Iterative DFS with explicit path state

Stack of (node, max_so_far) pairs.

Python

def good_nodes(root):
    if not root:
        return 0
    stack = [(root, float('-inf'))]   # L1: O(1) init
    count = 0
    while stack:
        node, mx = stack.pop()        # L2: O(1) pop
        if node.val >= mx:
            count += 1                # L3: O(1) count
        new_max = max(mx, node.val)   # L4: O(1) update
        if node.left:
            stack.append((node.left, new_max))   # L5: O(1) push
        if node.right:
            stack.append((node.right, new_max))  # L6: O(1) push
    return count

Swift

final class Solution { func goodNodes(_ root: TreeNode?) -> Int { guard let root else { return 0 }; var stack: [(TreeNode, Int)] = [(root, root.val)], total = 0; while let entry = stack.popLast() { if entry.0.val >= entry.1 { total += 1 }; let maximum = max(entry.1, entry.0.val); if let left = entry.0.left { stack.append((left, maximum)) }; if let right = entry.0.right { stack.append((right, maximum)) } }; return total } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L2 (pop)	$O(1)$	n	$O(n)$
L3/L4 (check + update)	$O(1)$	n	$O(n)$
L5/L6 (push children)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Complexity

• Time: $O(n)$.
• Space: $O(h)$.

Summary

Approach	Time	Space
Ancestor walks	$O(n · h)$	$O(n)$
DFS with running max	$O(n)$	$O(h)$
Iterative DFS with state	$O(n)$	$O(h)$

The recursive path-state DFS is the canonical answer and the template for many “longest increasing path” / “valid-along-path” tree problems.

Test cases

Python

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def good_nodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0
        good = 1 if node.val >= max_so_far else 0
        new_max = max(max_so_far, node.val)
        return good + dfs(node.left, new_max) + dfs(node.right, new_max)
    return dfs(root, float('-inf'))

def _run_tests():
    assert good_nodes(build_tree([3, 1, 4, 3, None, 1, 5])) == 4
    assert good_nodes(build_tree([3, 3, None, 4, 2])) == 3
    assert good_nodes(build_tree([1])) == 1
    # 5 (good), 6 (good, >=5), 7 (good, >=6); 4 and 3 not good
    assert good_nodes(build_tree([5, 4, 6, 3, None, None, 7])) == 3
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function goodNodes(root: TreeNode | null): number {
    function dfs(node: TreeNode | null, maxSoFar: number): number {
        if (!node) return 0;
        const good = node.val >= maxSoFar ? 1 : 0;
        const newMax = Math.max(maxSoFar, node.val);
        return good + dfs(node.left, newMax) + dfs(node.right, newMax);
    }
    return dfs(root, -Infinity);
}

console.assert(goodNodes(buildTree([3, 1, 4, 3, null, 1, 5])) === 4);
console.assert(goodNodes(buildTree([3, 3, null, 4, 2])) === 3);
console.assert(goodNodes(buildTree([1])) === 1);
console.assert(goodNodes(buildTree([5, 4, 6, 3, null, null, 7])) === 3);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, path-state DFS pattern

Related concepts

• Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
• DFS, the depth first traversal habit of following one branch before returning.