Challenge: Count and Total

Lab Java Beginner 10 points

Read a binary tree and print three lines: the number of nodes, the total of all values, and the number of leaves. Write each as a small recursive method.

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

nodes: a, total: b, leaves: c on three lines.

Example

Input

Output

nodes: 6
total: 42
leaves: 3

Sample input available Sample output available

Editor

Java

Hints

Build TreeNode objects first (see the build method in the lesson note), then use node 0 as the root.

A leaf is a node whose left and right are both null.

Solution explanation

Each method visits every node once: O(n).

Show solution

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;
    }

    static int count(TreeNode n) {
        if (n == null) return 0;
        return 1 + count(n.left) + count(n.right);
    }

    static long total(TreeNode n) {
        if (n == null) return 0;
        return n.value + total(n.left) + total(n.right);
    }

    static int leaves(TreeNode n) {
        if (n == null) return 0;
        if (n.left == null && n.right == null) return 1;
        return leaves(n.left) + leaves(n.right);
    }

    public static void main(String[] args) {
        TreeNode root = build(new Scanner(System.in))[0];
        System.out.println("nodes: " + count(root));
        System.out.println("total: " + total(root));
        System.out.println("leaves: " + leaves(root));
    }
}

Output

Answer