Skip to content

Volume ITechnology

4.14.10 — Count Good Nodes in Binary Tree ​

LeetCode 1448 · Medium

The problem ​

A node is good if no node on the path from the root down to it holds a larger value. Count the good nodes.

      3
    /   \
   1     4         good: 3 (root), 4, 5, 3
  /     / \
 3     1   5

The root is always good, since its path is just itself.

To put this in plain English: you start at the top of the tree. As you walk down a path to a leaf, you keep track of the biggest number you've seen so far. If the node you just stepped on is at least as big as that maximum, it's a "good" node. How many good nodes are there in total?

Constraints to Keep in Mind: ​

  • 1 <= Number of nodes in the tree <= 10^5
  • -10^4 <= Node.val <= 10^4
  • The tree can be highly unbalanced.

The brute force, and where it wastes work ​

A naive way to do this without passing state would be to check every node's full path back to the root.

  • How it works: For each node in the tree, you somehow traverse from the root down to that node, finding the maximum value on that specific path. Then you check if the node is \ge that maximum.
  • Why it's too slow: If you do a fresh path-check for every single node, in a degenerate (line-like) tree of n nodes, the 1st node takes 1 step, the 2nd takes 2 steps, ..., the n-th takes n steps. That's O(n^2) time. Instead, we can just carry the maximum value with us as we walk down, doing it in O(n) time.

The pattern ​

Every problem before this one sent information up the tree — a depth, a sum, a yes or no computed from the children. This one sends information down: each node needs to know the largest value seen on the way to it.

That is the other half of tree recursion, and knowing which direction a problem needs is most of the skill.

  • Information flowing down — pass it as an extra argument. Path state, depth, an allowed range.
  • Information flowing up — return it. Depths, sums, counts, validity.

Here the maximum so far goes down as a parameter, and the count comes back up as a return value. Many problems use both at once.

The solution ​

python
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, best_so_far: int) -> int:  # (1)
            if not node:  # (2)
                return 0

            count = 1 if node.val >= best_so_far else 0  # (3)
            best_so_far = max(best_so_far, node.val)  # (4)

            count += dfs(node.left, best_so_far)  # (5)
            count += dfs(node.right, best_so_far)
            return count  # (6)

        return dfs(root, root.val)  # (7)
ts
function goodNodes(root: TreeNode): number {
  function dfs(node: TreeNode | null, bestSoFar: number): number {  // (1)
    if (!node) return 0;  // (2)

    let count = node.val >= bestSoFar ? 1 : 0;  // (3)
    bestSoFar = Math.max(bestSoFar, node.val);  // (4)

    count += dfs(node.left, bestSoFar);  // (5)
    count += dfs(node.right, bestSoFar);
    return count;  // (6)
  }

  return dfs(root, root.val);  // (7)
}

Line by line ​

(1) The helper takes the node and the biggest value seen on the way down to it. It returns how many good nodes are in this node's subtree. So information flows down through the second argument, and the count flows up through the return value.

(2) A missing node has no good nodes.

(3) Is this node good? It is good when its value is at least the biggest value on the path above it. If so, it counts as 1.

(4) Update the biggest value, ready to hand down to the children.

(5) Add the good nodes from both subtrees. Each child receives the updated biggest value.

(6) Return the total for this subtree to the caller.

(7) Start at the root. The root's path is just itself, so the starting "biggest so far" is its own value, and the root always counts as good.

>=, not >. A node equal to the largest so far is still good — no node on its path is larger. Getting this wrong quietly loses nodes in trees with repeated values.

Start with root.val, not with negative infinity. Either works, since the root is trivially at least equal to itself. Using root.val makes the intent clearer.

Each branch gets its own best_so_far. Because it is a parameter rather than a shared variable, the left and right subtrees each receive their own copy and cannot interfere. That is the advantage of passing state down instead of mutating something outside — backtracking is automatic. No undo step is needed, unlike the explicit pop() in 4.8.4, because nothing is shared to begin with.

Trace ​

For the example tree, walking down each path:

pathmaxima seengood?
33yes
3 → 13no, 1 < 3
3 → 1 → 33yes, 3 ≥ 3
3 → 43yes
3 → 4 → 14no
3 → 4 → 54yes

Four good nodes. Note the second 3 counts only because the comparison is >=.

Complexity ​

  • Time Complexity: O(n). We visit every node in the tree exactly once. At each node, we do O(1) work (a comparison, a max() call, and addition). Thus, total time is strictly linear.
  • Space Complexity: O(h) where h is the height of the tree. This is the memory used by the recursion call stack. In the worst case (a degenerate tree), h = n, making space O(n). In a perfectly balanced tree, h = \log n, making space O(\log n). No other extra memory is used.

Edge cases ​

  • One node. The root is good, so the answer is 1.
  • Values that only grow going down. Every node is good.
  • Values that only shrink going down. Only the root is good.
  • Equal values, like a path 3 → 3 → 3. All three are good, because the check is >=.
  • Negative values. No special case. Starting from root.val rather than 0 matters here: starting at 0 would wrongly mark a negative root as not good.

Where this goes next ​

Every problem where a value flows down a root-to-node path:

  • Path Sum — carry the running total down and check it at each leaf.
  • Sum Root to Leaf Numbers — carry the digits built so far.
  • Validate Binary Search Tree — carry the allowed (min, max) range down, which is 4.14.11 and the clearest example of the technique.
  • Path Sum II — carry the path itself, and here you do need an undo, because a single list is shared to avoid copying at every node.

The rule: decide before writing whether the information flows down or up. Down goes in the parameters, up goes in the return value. Problems needing both do both.

What the interviewer will push on ​

"Which direction does information flow here?" Down, as a parameter. Say it before you code.

"Why >=?" A node equal to the maximum is still good.

"Why is no undo needed?" Each recursive call gets its own copy of the parameter, so branches cannot interfere.

"When would you need an undo?" When the state is a shared mutable structure, like a path list you are appending to.

One thing to volunteer: name the down-versus-up distinction explicitly. It is the single most useful frame for the whole tree chapter, and it makes the two hard problems later look routine.

Next: 4.14.11 Validate Binary Search Tree — passing a range downward, and the wrong answer nearly everybody gives first.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet