Google Code Jam 2014: Full Binary Tree

Question

Here is my entry for the Code Jam problem Full Binary Tree (I didn't compete but tackled the problem afterwards). It does solve the provided inputs, so I suppose it is correct. I am looking for any suggestions regarding the code. One thing I don't like is the fact that the Node constructor clears the array that it receives as a parameter, do you see a clean way to fix this ? Is it possible without declaring an extra class wrapping Node ?

import java.util.*;


class Node {
    static NodeComparator cmp = new NodeComparator();

    private ArrayList<Node> children = new ArrayList<>();
    private int nDescendants = 0;    // descendants = number of children and, recursively, children of children, etc.

    public int getNDescendants() {
        return nDescendants;
    }

    // turns the tree into a full binary tree by removing as few nodes as possible
    public void makeFullBinary() {
        // first, recursively make all the children into full binary trees
        for (Node n : children) {
            n.makeFullBinary();            
        }
        // sort the children from least to most number of descendants
        Collections.sort(children, cmp);
        // remove descendants as needed to end up with 0 or 2
        while ((children.size() != 0) && (children.size() != 2)) {
            children.remove(0);
        }
        // recompute the number of descendants
        nDescendants = 0;
        for (Node c : children) {
            nDescendants += 1 + c.getNDescendants();
        }
    }

    // builds a tree from an array of booleans (adjacency matrix)
    // edges is destroyed after the constructor is called
    public Node(boolean[][] edges, int root) {
        for (int i = 0; i < edges.length; i++) {
            if (edges[root][i]) {
                edges[root][i] = false;
                edges[i][root] = false;
                children.add(new Node(edges, i));
            }
        }
        for (Node c : children) {
            nDescendants += 1 + c.getNDescendants();            
        }
    }
}

// comparator for sorting only
class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n0, Node n1) {
        return n0.getNDescendants() - n1.getNDescendants();
    }    
}

public class Program {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int nCases = in.nextInt();
        in.nextLine();

        for (int caseNumber = 1; caseNumber <= nCases; caseNumber++) {
            int nNodes = in.nextInt();
            in.nextLine();

            boolean[][] edges = new boolean[nNodes][nNodes];

            for (int i = 0; i < nNodes-1; i++) {
                String[] s = in.nextLine().split(" ");
                int x = Integer.parseInt(s[0])-1;
                int y = Integer.parseInt(s[1])-1; 
                edges[x][y] = true;
                edges[y][x] = true;
            }

            int maxDescendants = 0;
            boolean [][] e = new boolean[nNodes][nNodes];
            for (int i = 0; i < nNodes; i++) {                
                for (int a = 0; a < nNodes; a++) {
                    for (int b = 0; b < nNodes; b++) {
                        e[a][b] = edges[a][b];
                    }
                }
                Node tree = new Node(e, i);
                tree.makeFullBinary();
                maxDescendants = Math.max(maxDescendants, tree.getNDescendants());
            }            

            System.out.print("Case #");
            System.out.print(caseNumber);
            System.out.print(": ");
            System.out.println(nNodes - maxDescendants - 1);
        }
        in.close();
    }
}

Answer 1

Oke I'm going to have with this review the point of javadoc, namings and methods.

First :

You make comment, what is actually good but try to make javadoc in stead of commenting everything.

// comparator for sorting only
class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n0, Node n1) {
        return n0.getNDescendants() - n1.getNDescendants();
    }    
}

should be :

/**
* Comparator for sorting on descendants
*/
class NodeComparatorNDescendants implements Comparator<Node> {
    @Override
    public int compare(Node n0, Node n1) {
        return n0.getNDescendants() - n1.getNDescendants();
    }    
}

Why :

This cause you no more effort than commenting, but you can generate a complete javadoc what other persons can look into.
Also see that I added the on what you are sorting there.
At last I changed also the class name.
Now you will already see without the javadoc on what you will compare.
Note : Effective class name helps you later also, take this code after a year not seen and you will need to see the implementation of the comparator if you want to know on what it compares.

Second :

Like I already said in the first point, naming is everything.
Node n => why just not Node node. Other example : NodeComparator cmp => NodeComparator nodeComparator
This will not take more memory from your program if you have fear for that :), and if you use autocomplete this will not lose time to program.

Thirth :

Small effective methods are better than big ones that do a lot.
How less code in a method => the sooner you find the bug because your method complexity is lower.

Example :

// turns the tree into a full binary tree by removing as few nodes as possible
public void makeFullBinary() {
    // first, recursively make all the children into full binary trees
    for (Node n : children) {
        n.makeFullBinary();            
    }
    // sort the children from least to most number of descendants
    Collections.sort(children, cmp);
    // remove descendants as needed to end up with 0 or 2
    while ((children.size() != 0) && (children.size() != 2)) {
        children.remove(0);
    }
    // recompute the number of descendants
    nDescendants = 0;
    for (Node c : children) {
        nDescendants += 1 + c.getNDescendants();
    }
}

should be :

// turns the tree into a full binary tree by removing as few nodes as possible
public void makeFullBinary() {

    createBinaryTree();
    Collections.sort(children, cmp);
    adjustBinaryTree();
    recalculateDescendants();
}

private void createBinaryTree () {
    for (Node n : children) {
        n.makeFullBinary();
    }
}

private void adjustBinaryTree () {
    while ((children.size() != 0) && (children.size() != 2)) {
        children.remove(0);
    }
}

private void recalculateDescendants () {
    nDescendants = 0;
    for (Node c : children) {
        nDescendants += 1 + c.getNDescendants();
    }
}

Why :

Each method is shorter then the whole method.
It's easier to read and to comprehent the actual doing of the method.
Now there is just one thing what bothers me, but it is an discussion amoung programmers, that's the reason I didn't changed it but still going to say
nDescendants is a calculated field.
For more rightness you should remove the int and set the recalculateDescendants code in the getNDescendants().
Yes you lose performance and you gain an always correctness of the getter.
Now you see directly why there are always discussions about that.

Hope this helps you already to improve yourself.