Count Balanced Nodes in a Rooted Tree
Reported by candidates from DRW's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The data structure that matters in this DRW question from September 2026 is the tree itself, specifically a subtree-size array filled by a post-order walk. You get an adjacency list, node 0 is the root, and you count nodes whose child subtrees all have the same size. It looks like a tree problem and it is, but the whole thing is one traversal and a comparison. If you've got an OA invite and 48 hours, this is a pattern worth knowing cold. StealthCoder sits invisibly on your screen during the live assessment as a safety net if you blank on the recursion, but the logic below is short enough to carry in your head.
The problem
You are given a rooted tree represented by an adjacency list subtrees. Node 0 is the root, and subtrees[i] lists the indices of the immediate children of node i. The size of a subtree is the number of nodes it contains, including the node at its root. A node is balanced if all of its immediate child subtrees have the same size. A node with zero or one child is balanced. Return the number of balanced nodes in the tree. Function solution(subtrees: int[][]) → int Examples Example 1 subtrees = [[1,2],[3,4],[5],[],[],[]] return = 5 Node 0 has child-subtree sizes 3 and 2, so it is not balanced. Every other node is balanced, giving a total of 5. Example 2 subtrees = [[1,2,3],[],[],[]] return = 4 The root has three child subtrees of size 1. The root and all three leaves are balanced. Example 3 subtrees = [[1,2],[3],[5,6],[4],[],[],[]] return = 7 The two subtrees below the root both have size 3, even though their shapes differ. Every node is balanced. Constraints subtrees is non-empty and contains one row for every node. Node 0 is the root. Every child index is a valid index into subtrees. Every node other than node 0 appears exactly once among the child lists, node 0 never appears as a child, and the representation contains no cycle. The order of indices within a child list does not affect the result.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is computing subtree sizes bottom-up. Run a DFS from node 0. For each node, recurse into every child, collect their sizes, and check whether they're all equal. Size of the node is 1 plus the sum of child sizes. If the child sizes match, or there are zero or one children, increment a counter. Return the size upward. That's O(n) total. The common pitfall is comparing shapes instead of sizes. Example 3 shows two different shaped subtrees that both have size 3, and they still count as balanced. Another pitfall is recursion depth. A chain of thousands of nodes can blow the stack in some languages, so an iterative post-order is safer. Also don't recompute sizes per node, that turns it into O(n^2). If you freeze during the live OA, StealthCoder can hand you the post-order skeleton, but you should be able to write it yourself.
StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.
You can drill Count Balanced Nodes in a Rooted Tree cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. If you're reading this with an OA window open, you're who this was built for.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass DRW's OA.
DRW reuses patterns across OAs. If you're reading this with an OA window open, you're who this was built for. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Count Balanced Nodes in a Rooted Tree FAQ
What's the trick to the DRW balanced nodes problem?+
Compute subtree sizes with a post-order DFS. At each node, gather the sizes of its children, check they're all equal, and return 1 plus their sum. Count the node as balanced when the sizes match or it has fewer than two children. One pass, O(n).
How hard is this problem really?+
Easy to medium. There's no fancy algorithm. If you're comfortable with recursion on trees, it's a few lines. The difficulty is in reading the definition carefully: it's about sizes of child subtrees, not their structure, and leaves count as balanced.
Do two child subtrees with different shapes count as balanced?+
Yes. Only the node count matters. Example 3 shows this: the root's two child subtrees both have three nodes but different shapes, and the root is still balanced. Don't write any shape comparison or hashing logic.
Should I use recursion or an iterative approach?+
Recursion is fine for most inputs and it's the fastest to write. If the tree could be a long chain, depth might overflow the stack, so an iterative post-order with an explicit stack is safer. Mention this tradeoff if you're explaining your approach.
How do I prepare for this in 48 hours?+
Write the subtree-size DFS from scratch two or three times on different trees, including a chain, a star, and a mixed one. Test against the three examples. Then practice the same pattern on nearby tree questions so the post-order return value feels automatic.