Skip to content

085 — Count Good Nodes in Binary Tree

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

85 — Count Good Nodes in Binary Tree

LeetCode 1448 · Medium. Given the root of a binary tree, a node X is good if, along the path from the root to X, no node has a value greater than X's value. Return the number of good nodes.

🍽️ Intuition

Imagine climbing from the root down to some node and keeping a running note of "the highest value I've seen so far on this climb." A node is "good" if it's at least as tall as everything that came before it on the way down — it doesn't have to beat the whole tree, just its own ancestors. The catch is that "everything above me" is different for every node, so the naive approach re-climbs from the root for every single node just to find that node's personal maximum-so-far.

🚩 Pattern-Recognition Cue

"Along the path from the root to X" / "no ancestor is larger" is the cue for a top-down DFS that carries extra state down through the recursion — specifically, "the maximum value seen on the path so far" gets passed as a parameter into each recursive call, rather than recomputed by re-walking from the root every time.

🐢 Brute Force

For every node in the tree, separately re-walk from the root down to that specific node to reconstruct its root-to-node path, then check whether the node's value is at least the max of everything before it on that path.

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func collectAllNodes(_ node: TreeNode?, _ result: inout [TreeNode]) {
    guard let node = node else { return }
    result.append(node)
    collectAllNodes(node.left, &result)
    collectAllNodes(node.right, &result)
}

// re-walks from root every time, looking for `target` by reference identity
func pathFromRoot(_ root: TreeNode?, _ target: TreeNode) -> [Int] {
    guard let root = root else { return [] }
    if root === target { return [root.val] }

    let leftPath = pathFromRoot(root.left, target)
    if !leftPath.isEmpty { return [root.val] + leftPath }

    let rightPath = pathFromRoot(root.right, target)
    if !rightPath.isEmpty { return [root.val] + rightPath }

    return []
}

func countGoodNodesBruteForce(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    var allNodes: [TreeNode] = []
    collectAllNodes(root, &allNodes)

    var count = 0
    for node in allNodes {
        let path = pathFromRoot(root, node)
        let maxBeforeNode = path.dropLast().max() ?? Int.min
        if node.val >= maxBeforeNode {
            count += 1
        }
    }
    return count
}

// smoke test:        3
//                 /     \
//                1       4
//               /       / \
//              3       1   5
let bfRoot = TreeNode(3)
bfRoot.left = TreeNode(1); bfRoot.right = TreeNode(4)
bfRoot.left?.left = TreeNode(3)
bfRoot.right?.left = TreeNode(1); bfRoot.right?.right = TreeNode(5)
print(countGoodNodesBruteForce(bfRoot))   // 4 -> good: 3(root), 4, 3(left grandchild, ties root), 5

Big-O: O(n²) time in the worst case — pathFromRoot re-walks from the root for every one of the n nodes, and each such walk can cost O(n) on a skewed tree. O(h) extra space per pathFromRoot call, though the outer loop and node collection add O(n) overall.

🚀 Optimal

Do a single top-down DFS that carries "the maximum value seen so far on this root-to-node path" as a parameter. At each node, check the node's value against that running max, then pass the updated max down into both children.

func countGoodNodes(_ root: TreeNode?) -> Int {
    func dfs(_ node: TreeNode?, _ maxSoFar: Int) -> Int {
        guard let node = node else { return 0 }

        let isGood = node.val >= maxSoFar ? 1 : 0
        let newMax = max(maxSoFar, node.val)

        return isGood + dfs(node.left, newMax) + dfs(node.right, newMax)
    }

    return dfs(root, Int.min)
}

// smoke test: same tree as above
let root = TreeNode(3)
root.left = TreeNode(1); root.right = TreeNode(4)
root.left?.left = TreeNode(3)
root.right?.left = TreeNode(1); root.right?.right = TreeNode(5)
print(countGoodNodes(root))   // 4

print(countGoodNodes(nil))   // 0 — empty tree has no nodes at all

// single node
print(countGoodNodes(TreeNode(7)))   // 1 — the root is always good (nothing above it)

Big-O: O(n) time — every node is visited exactly once, carrying its ancestor-max down as a parameter instead of re-deriving it. O(h) extra space for the recursion stack.

🔑 The Key Insight

The brute force treats "what's the max on my path from the root" as something that has to be rediscovered for every node, by walking from the root all over again. But that running max is exactly the kind of information a parent already has and can simply hand down to its children — it never needs to be recomputed, only carried forward and updated (max(maxSoFar, node.val)) as the recursion descends. Passing state downward through the call stack, instead of re-deriving it from scratch at every node, is what collapses O(n²) into O(n).

🔗 Related Chapters

  • Binary Trees — the structure being walked.
  • DFS and Backtracking — the single top-down pass carrying extra state (the running max) down through the recursion parameters.
  • Big-O Notation — for the O(n²) vs. O(n) contrast above.

🧸 Memory Sentence

Count Good Nodes is climbing down from the root with a running note of "the tallest I've seen so far" tucked in your pocket — hand that note to each child instead of asking them to climb back up and re-check for themselves.

✅ Check Your Understanding

Trace the optimal dfs on the tree 3 -> (1 -> (3), 4 -> (1, 5)), writing down the maxSoFar value passed into each recursive call and whether each node is counted as good. Why does the node with value 1 at depth 2 (child of the node 1 at depth 1) fail to be good, even though it's greater than its immediate parent?

⬅️ Previous: Binary Tree Right Side View · Next: Validate Binary Search Tree ➡️

Clone this wiki locally