2265. Count Nodes Equal to Average of Subtree

This one introduces trees and recursion-on-trees for the first time in this series — a big new shape of problem. Let's build it up carefully from zero.

---

1. Problem in Very Simple Language

You're given a binary tree — we'll explain exactly what that is in a moment. Every node in the tree holds a number (INLINECODE0).

For every single node in the tree, consider its subtree — that node itself, plus every node "hanging below" it (its children, their children, and so on, all the way down). Compute the average of all the values in that subtree: add up every value in the subtree, divide by how many nodes are in the subtree, and round down to the nearest whole number (drop any decimal part).

Then check: does this node's own value equal that computed average?

Goal: count how many nodes, across the entire tree, satisfy "my own value equals the average of my subtree." What's given: the root of a binary tree. What to find: for every node, whether its value matches its subtree's average. What to return: the total count of nodes where this is true.

---

2. Real-Life Analogy

Imagine a company org chart, shaped like a tree: a CEO at the top, with managers below them, and employees below the managers, and so on. Every person has a "performance score" (their value).

For every single person in the org chart, imagine you gather that person plus everyone who reports to them, directly or indirectly (their whole "team," including sub-teams) — and compute the average performance score of that entire team (rounding down).

You want to count: how many people have a performance score that exactly equals the average score of their own team (including themselves)? A brand-new hire with no reports is automatically their "own team of one," so their score trivially equals their team's average (themselves).

---

3. Important Programming Concepts I Need First

Binary Tree

Concept: A tree where each node has at most two children, conventionally called INLINECODE1 and INLINECODE2. There's one special node at the very top called the INLINECODE3, and nodes with no children are called "leaves." Example: A node with INLINECODE4, whose INLINECODE5 child has INLINECODE6 and whose INLINECODE7 child is INLINECODE8 (meaning "no right child"). Why we need it: The input to this problem is exactly this kind of structure — we must navigate it using INLINECODE9 and INLINECODE10, not array indices.

TreeNode (the building block)

Concept: Each node is an object with three parts: INLINECODE11 (its number), INLINECODE12 (a reference to its left child, or INLINECODE13 if none), and INLINECODE14 (same idea, for the right child). Why we need it: We'll be constantly reading INLINECODE15 and following INLINECODE16/INLINECODE17 to explore the tree.

Subtree

Concept: The subtree "rooted at" some node INLINECODE18 consists of INLINECODE19 itself, plus everything reachable by following INLINECODE20/INLINECODE21 pointers downward from INLINECODE22 — i.e., all of INLINECODE23's descendants. A leaf node's subtree is just itself (a "team of one"). Why we need it: The entire problem is defined in terms of "average of a node's subtree" — we need to be crystal clear that this always includes the node itself.

Recursion on Trees (a very natural fit)

Concept: Trees are naturally recursive structures: "the tree rooted at node X" = "node X itself" + "the tree rooted at X.left" + "the tree rooted at X.right." This means a recursive function that solves a problem for a whole tree can often be built by (a) solving the same problem for the left and right subtrees first, and (b) combining those results with the current node's own value. Simple Example: To count all nodes in a tree: INLINECODE24, with the base case INLINECODE25. Why we need it: Computing "sum and count of every subtree," for every node, is a textbook recursive-on-trees problem — each node's subtree sum/count is built directly from its children's subtree sums/counts.

Base Case (for tree recursion specifically)

Concept: The natural "smallest" input for tree recursion is INLINECODE26 — an empty/nonexistent node (like "no child here"). We must decide what our function should return for INLINECODE27, since every recursive tree function eventually reaches this case as it walks down to the leaves and beyond. Why we need it: Without a correct base case for INLINECODE28, our recursion would either crash (trying to read INLINECODE29 on something that doesn't exist) or never terminate.

Returning Multiple Values from One Recursive Call

Concept: Sometimes a single recursive call needs to report back more than one piece of information to its caller (here: both the subtree's sum AND its node count). In Java, a clean way to do this is to return a small array (like INLINECODE30), or in JavaScript an array INLINECODE31. Why we need it: For each node, we need both the total sum and the total count of its subtree to compute the average — a single return value isn't enough.

---

4. Understand the Input

Take Example 1: CODEBLOCK0

This array notation represents a binary tree, level by level (this is LeetCode's standard way of describing trees as flat arrays). Drawn out as an actual tree:

CODEBLOCK1

The root node has value INLINECODE32, with left child INLINECODE33 and right child INLINECODE34. Node INLINECODE35 has left child INLINECODE36 and right child INLINECODE37 (both leaves). Node INLINECODE38 has no left child (that's what the INLINECODE39 represents) and has right child INLINECODE40 (a leaf). We need to check, for every node in this tree, whether its own value equals the average of its entire subtree.

---

5. Understand the Output

Output: INLINECODE41

Let's check every node (there are 6 total: INLINECODE42):

Node 4 (root): its subtree is the entire tree: INLINECODE43. Sum = INLINECODE44, count = INLINECODE45, average = INLINECODE46. Does INLINECODE47? Yes. Node 8: its subtree is INLINECODE48. Sum = INLINECODE49, count = INLINECODE50, average = INLINECODE51. Does INLINECODE52? No. Node 5: its subtree is INLINECODE53 (itself plus its right child, no left child). Sum = INLINECODE54, count = INLINECODE55, average = INLINECODE56 (integer division rounds down INLINECODE57 to INLINECODE58). Does INLINECODE59? Yes. Node 0: a leaf, subtree is just INLINECODE60. Average = INLINECODE61. Does INLINECODE62? Yes. Node 1: a leaf, subtree is just INLINECODE63. Average = INLINECODE64. Does INLINECODE65? Yes. Node 6: a leaf, subtree is just INLINECODE66. Average = INLINECODE67. Does INLINECODE68? Yes.

Counting the "Yes" answers: node 4, node 5, node 0, node 1, node 6 — that's 5 nodes. Only node INLINECODE69 fails to match. ✔️ matches the expected output!

Notice: every leaf automatically matches (its subtree is just itself, so the average always trivially equals its own value) — this is a useful sanity-check pattern to keep in mind.

---

6. Solve the Example Manually

Let's manually trace through how we'd compute this recursively, from the bottom up (since we can't know a node's subtree sum until we know its children's subtree sums first).

We process nodes in an order where children are fully handled before their parents (this is naturally how recursion unwinds):

Counting the ✔️ marks: INLINECODE70 — that's 5 matches (node INLINECODE71 is the only failure). ✔️ Total: 5, matching the expected output!

---

7. Think Like a Programmer

What do I know? For any node, if I already know the (sum, count) of its left subtree and right subtree, I can instantly compute its own subtree's (sum, count): INLINECODE72, INLINECODE73. What do I need to find? For every node, whether INLINECODE74 (integer division). What can I try? A recursive function that, for a given node, first recursively computes its left child's (sum, count) and right child's (sum, count), then combines them with its own value to get its own (sum, count) — and along the way, checks the matching condition and updates a running counter. What's the base case? A INLINECODE75 node contributes INLINECODE76 to whatever called it — this correctly represents "there's nothing here to add." What order must things happen in? We must fully finish processing a node's children before we can compute that node's own subtree sum/count — this is naturally what post-order traversal provides. How do I count matches across the WHOLE tree? Use a counter variable that gets incremented every time a node's condition is satisfied during the recursive traversal.

---

8. Start With the Brute Force Solution

Naive idea: For each node, separately walk its entire subtree from scratch to compute the sum and count, then compare to its value.

Why it's correct but wasteful: A node near the root has its subtree scanned, then each of its children's subtrees get scanned again separately — leading to $O(N^2)$ work on skewed trees.

CODEBLOCK2

CODEBLOCK3

---

9. Explain the Naive Code Line by Line

INLINECODE77 — a running total of how many nodes satisfy the condition, tracked as we go. INLINECODE78 — kicks off a traversal that visits every node in the tree, one at a time. Inside INLINECODE79: INLINECODE80 — base case, nothing to check for a non-existent node. INLINECODE81 — for the current node, do a completely separate, full recursive scan of its entire subtree just to get its sum and count. INLINECODE82 — check the matching condition, using integer division. INLINECODE83 — recursively check children, each triggering full sub-traversals.

---

10. Why Is This Naive Approach Not Ideal?

Imagine a tree shaped like a long chain (each node has exactly one child, going 1000 nodes deep). For the topmost node, INLINECODE84 walks 1000 nodes. For the second, it walks 999 nodes. Total work: roughly INLINECODE85 operations ($O(N^2)$). We can eliminate all repeated rescans by computing the aggregate bottom-up in a single pass.

---

11. Find the Better Approach

CODEBLOCK4

---

⭐ Key Insight

Before the insight

It feels like we need two separate steps: first get every node's subtree sum/count; second, use that info to check matches.

The problem

Doing these as two separate traversal passes leads to repeated $O(N^2)$ sub-scans.

The insight

A single post-order recursive function can compute a subtree's INLINECODE86 AND check-and-count the matching condition for that node, all in one pass. By the time INLINECODE87 and INLINECODE88 return their pairs to INLINECODE89, we immediately know INLINECODE90's subtree sum and count, evaluate INLINECODE91, increment the counter, and return INLINECODE92's aggregated pair to its parent.

After the insight

Every node in the tree is processed exactly once in $O(1)$ time per node, scaling in $O(N)$ total time.

---

13. Dry Run the Optimized Solution

Let's dry-run Example 2: INLINECODE93 (single node).

Call on root (INLINECODE94): INLINECODE95 is INLINECODE96, INLINECODE97 is INLINECODE98. Recursive call on INLINECODE99 (INLINECODE100) → returns INLINECODE101. Recursive call on INLINECODE102 (INLINECODE103) → returns INLINECODE104. Combine: INLINECODE105, INLINECODE106. Check: INLINECODE107. INLINECODE108 → Match! INLINECODE109. Return INLINECODE110. Output = INLINECODE111. ✔️

---

14. Optimized Code

CODEBLOCK5

CODEBLOCK6

---

15. Explain Optimized Code Line by Line

INLINECODE112 — accumulator variable across the entire traversal. INLINECODE113 — initiates traversal on root and returns final count. INLINECODE114 — base case: null subtree contributes 0 sum and 0 count. INLINECODE115 & INLINECODE116 — post-order traversal: resolve child subtrees first. INLINECODE117 — aggregates current node with left and right sums. INLINECODE118 — aggregates node count (1 for current node + child counts). INLINECODE119 — computes integer rounded-down average. INLINECODE120 — tests condition and increments match counter. INLINECODE121 — passes accumulated subtree statistics to parent.

---

16. Test With Multiple Examples

Example 1 — Normal Case

INLINECODE122 → 5 matches (nodes 0, 1, 6, 5, 4) → Output: INLINECODE123 ✔️

Example 2 — Different Case

INLINECODE124 → 1 match → Output: INLINECODE125 ✔️

Example 3 — Single-child tree

INLINECODE126 → Leaf 2 matches (avg 2), root 1 matches (avg (1+2)/2 = 1) → Output: INLINECODE127 ✔️

---

17. Edge Cases

Single node: Always matches (avg equals node value) → returns INLINECODE128. All leaves in any tree: Always match trivially. All equal values: Every subtree average equals that same value → returns total node count $N$. Skewed / Degenerate tree (linked list structure): Handled in $O(N)$ without stack overflow within problem constraints ($N \le 1000$).

---

18. Time Complexity

Optimized Solution: $O(N)$ — every node is visited exactly once, doing $O(1)$ operations per node. Naive Rescan: $O(N^2)$ in worst-case skewed trees.

---

19. Space Complexity

Call Stack Space: $O(H)$, where $H$ is the height of the tree. Balanced tree: $O(\log N)$ Skewed tree: $O(N)$ Auxiliary Variables: $O(1)$.

---

20. Common Mistakes Beginners Make

❌ "Floating-point division is required." ✅ Integer division / INLINECODE129 naturally rounds down as specified. ❌ "Subtree excludes the current node." ✅ A subtree rooted at $X$ includes $X$ itself plus all its descendants. ❌ "Using two separate traversals." ✅ Bottom-up post-order combines statistics gathering and condition verification in one single pass.

---

21. How to Recognize This Pattern in Other Problems

Watch for: CODEBLOCK7 Whenever a parent needs aggregated metrics from its children, use post-order DFS returning a multi-value tuple INLINECODE130.

---

22. Interview Thinking

CODEBLOCK8

---

23. Mini Challenge

Try these before checking the answers:

1. Why must we fully compute INLINECODE131 and INLINECODE132 before computing INLINECODE133 and INLINECODE134? 2. If a node has INLINECODE135 and INLINECODE136, what is the computed average, and would it match node value 4? 3. Why does every leaf node automatically match?

Answer to Mini Challenge

1. A parent's subtree statistics are defined as the sum of its children's subtree statistics plus its own; children must finish first. 2. INLINECODE137 (integer division). It matches value 3, but does not match value 4. 3. For any leaf, INLINECODE138 and INLINECODE139, so INLINECODE140.

---

24. Final Revision

🧠 Problem in One Sentence

Count how many nodes in a binary tree have a value equal to the rounded-down average of all values in their own subtree.

🔑 Main Idea

A single post-order recursive traversal computes each node's subtree INLINECODE141 bottom-up and verifies the average condition on the fly in $O(N)$ time.

⚙️ Algorithm

1. Base case: INLINECODE142 returns INLINECODE143. 2. Recursively get INLINECODE144 and INLINECODE145. 3. INLINECODE146; INLINECODE147. 4. If INLINECODE148, increment INLINECODE149. 5. Return INLINECODE150.

⏱️ Complexity

Time: $O(N)$ Space: $O(H)$

---

25. Beginner Quiz

1. (Understanding) Why does a subtree's definition always include the node itself, not just its descendants? 2. (Basic concept) What does the base case INLINECODE151 for a INLINECODE152 node represent, in plain words? 3. (Logic) Why can we safely check and count the current node's matching condition before* returning its (sum, count) to its parent, rather than needing some separate later pass? 4. (Dry run) For a tree INLINECODE153 (root value 2, left child value 2, right child value 2), compute the (sum, count) at each node and determine the final answer. 5. (Complexity/pattern) Why would the naive "rescan each subtree separately" approach be $O(N^2)$ for a chain-shaped tree specifically, and what general tree-problem signal should make you reach for a single combined post-order traversal instead?