Google Code Jam 2014: Full Binary Tree

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 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 {
@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();

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 {
    @Override
    public int compare(Node n0, Node n1) {
        return n0.getNDescendants() - n1.getNDescendants();
    }    
}

should be :

/**
* Comparator for sorting on descendants
*/
class NodeComparatorNDescendants implements Comparator {
    @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.

StackExchange Code Review Q#48803, answer score: 3