Binary Tree Level Order Sum

Problem Statement

You're given a binary tree encoded as a flat array: position 0 is the root, and for any position i that holds a real node, its left child lives at position 2*i + 1 and its right child at position 2*i + 2 — if either of those positions is marked N (or falls off the end of the array), that child simply doesn't exist, and neither do any of its own descendants. Compute the sum of the node values at each depth of the tree, starting from the root, and print those sums in order, one per depth.

Input Format

The input has exactly two lines:

• Line 1: a single integer n, the length of the array.
• Line 2: n space-separated tokens, each either an integer (a node's value) or the literal N (no node at that position).

Output Format

Print one line containing the sum of node values at each depth of the tree, from depth 0 (the root) downward, separated by single spaces. Print a sum for exactly as many depths as the tree actually has real nodes at — stop once a depth would contain no real nodes at all.

Example Walkthrough

Take the first sample: array 1 2 3 4 N N 5 (positions 0 through 6). Position 0 holds 1 — that's the root, depth 0, so depth 0's sum is 1. Its children are positions 1 and 2: position 1 holds 2, position 2 holds 3, both real, so depth 1's sum is 2 + 3 = 5. Now look at depth 2, the children of positions 1 and 2: position 1's children are positions 3 and 4 — position 3 holds 4 (real), position 4 is N (no node, and so no children of its own either); position 2's children are positions 5 and 6 — position 5 is N, position 6 holds 5 (real). So depth 2's real values are 4 and 5, summing to 9. The only positions left to consider are the children of positions 3 and 6 (since 4 and 5 have no real nodes), which would need positions 7 and beyond — outside the array entirely — so there's no depth 3 at all. The final sums are 1 5 9.

Approach

It helps to think of this as visiting the array starting from position 0, carrying along the depth of whatever position is currently being visited (the root starts at depth 0, and every child visited is always exactly one depth deeper than its parent — a simple depth + 1 passed down at each step, never recomputed from scratch). At each position, first check whether it's actually in range and not marked N. If it isn't a real node, stop there: don't add anything, and — just as importantly — don't go looking at its children either, since a nonexistent node can't have children of its own, no matter what values happen to sit at those array positions.

If the position does hold a real node, add its value into that depth's running sum. The very first time a real node is found at a given depth, that depth's sum starts at 0 before the node's value is added; every later real node found at the same depth (from a different branch of the tree) just adds into the sum that's already there. After handling the current node, continue on to its two children at depth + 1.

The reason this naturally stops at the right depth — without needing to explicitly say "the tree has this many levels" — is that a depth's sum only ever gets created when a real node is actually found there. If every position at some depth turns out to be missing or out of range, that depth never gets a sum created for it at all, and there's nothing to print for it or for anything deeper (since a tree with no nodes at depth d cannot have any nodes at depth d + 1 either, as every node at depth d + 1 would need a real parent at depth d).

Common Mistakes

• Recording a sum of 0 for a depth that has no real nodes at all. It's tempting to process the tree level by level and simply record whatever total was computed at each level, even when every position visited at that level turned out to be N or out of range. That produces an extra, incorrect trailing 0 in the output — a depth should only appear in the output if it actually contains at least one real node.
• Treating a node value of 0 as if it were the same as N. A real node can perfectly well have the value 0 — it still needs to be counted and still has children to visit. A check like if tree[i]: would incorrectly skip it, since 0 is falsy in Python, even though tree[i] is None (meaning genuinely no node) is the condition that actually matters here.
• Visiting the children of a position that's N or out of range. Since child positions are computed purely from index arithmetic (2*i + 1, 2*i + 2), it's possible to compute a valid array index for the "child" of a position that doesn't hold a real node, and that position might coincidentally hold some leftover integer value. That value must never be counted — a position only has real children if it holds a real node itself.