Challenge: Level Totals

Lab Java Intermediate 20 points

Read a binary tree and print the total of the values on each level, from the root level down, separated by spaces. Use a queue and the “size at the start of the level” trick.

Input

Line 1: n, the number of nodes (numbered 0 to n − 1; node 0 is the root). Then n lines, one per node in order: value left right, where left and right are child node numbers, or -1 for no child.

Output

One total per level, separated by spaces.

Example

Input

Output

8 13 21

Sample input available Sample output available

Editor

Java

Hints

Start the queue with the root.

At the start of each level, size = queue.size(); poll exactly that many nodes and add up their values.

Solution explanation

Every node enters and leaves the queue once: O(n).

Show solution

import java.util.ArrayDeque;
import java.util.Scanner;

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class Main {
    static TreeNode[] build(Scanner sc) {
        int n = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n];
        int[] left = new int[n], right = new int[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new TreeNode(sc.nextInt());
            left[i] = sc.nextInt();
            right[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            if (left[i] != -1) nodes[i].left = nodes[left[i]];
            if (right[i] != -1) nodes[i].right = nodes[right[i]];
        }
        return nodes;
    }

    public static void main(String[] args) {
        TreeNode root = build(new Scanner(System.in))[0];
        ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            int size = queue.size();
            long total = 0;
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                total += n.value;
                if (n.left != null) queue.offer(n.left);
                if (n.right != null) queue.offer(n.right);
            }
            if (sb.length() > 0) sb.append(' ');
            sb.append(total);
        }
        System.out.println(sb);
    }
}

Output

Answer