Sort an unordered tree by the amount of child-nodes a node has

Question

I'm currently working through "Algorithms in java" by Robert Sedgewick (3rd edition, german version) on my own and am trying to solve one of the exercises there, currently one from the "creative-solutions"-section.

As part of the solution of one exercise I'm trying to sort an unsorted tree by the amount of children each Node has, nodes with larger amounts of children coming first:

1. Sort all child-nodes of a parent n0 according to the amount of child-nodes nNodes that the child-nodes themselves have, sort from left to right from largest to lowest. Perform this sorting for all Nodes in the tree.
2. If 2 sibling-nodes n1 and n2 of these child-nodes have identical nNodes, go to the child-nodes of n1 and n2 try to sort these two according to the nNodesof their largest children. If no difference is found, try to sort according to the nNodesof their 2nd largest children, etc.
3. If you run out of children, go to the child-node of the child in 2 with the largest amount of children and repeat 2. etc. etc.
4. If after all comparisons it turns out that both n1 and n2 are roots of trees with identical shape, it doesn't matter which of the two comes first.

To give a visual comparison, this "rule" would result in the following tree sorting as depicted here: Example of Sorting.

The code

The problem I'm stuck at is correctly implementing the sorting. Each tree is composed of nodes. Each Node contains a value (so that you have a "name" for the node, not important for the sorting itself which only cares about the amount of children each node has) and an arrayList of Node-references to the child-nodes of that node. For nodes without children that ArrayList has size 0. The key here is sorting the ArrayLists in all of the Nodes, which I'm currently trying to do using the built-in sort method with a Comparator object. I think I have to approach this recursively, which makes the whole thing really messy because I'm currently having a comparator method calling itself while also calling "sort" for other ArraLists in the same method. The sortForest method below gives me stack-overflow errors when I'm trying it out in some main-methods to test it.

    static NodeComparator comp = new NodeComparator();

    static class Node {
        int value;
        ArrayList<Node> children;

        Node(int value, ArrayList<Node> children) {
            this.value = value;
            this.children = children;
        }
    }

    static class NodeComparator implements Comparator<Node> {
        public NodeComparator() {
        }

        public int compare(Node n1, Node n2) {
            /*-
             * Base Case 1: Both Nodes are leafs (isEmpty() is true) - they are
             * equal -> return 0.
             * Base Case 2/3: One of the Nodes is a leaf while the other isn't - 
             * the one that is a leaf is "lower" than the one that isn't. ->
             * return (-) 1. 
             */
            if (n1.children.isEmpty() && n2.children.isEmpty()) {
                return 0;
            } else if (n2.children.isEmpty()) {
                n1.children.sort(comp);
                return 1;
            } else if (n1.children.isEmpty()) {
                n2.children.sort(comp);
                return -1;
            } else {
                /* Get the amount of children the 2 nodes n1 and n2 have */
                int nChildren1 = (n1.children.isEmpty()) ? 0 : n1.children.size();
                int nChildren2 = (n2.children.isEmpty()) ? 0 : n2.children.size();
                /* Always sort the ArrayList of children that they have */
                n1.children.sort(comp);
                n2.children.sort(comp);

                /*
                 * If n1 and n2 have equal amounts of children, compare the
                 * amounts of children their children have, from largest to
                 * lowest
                 */
                if (nChildren1 == nChildren2) {
                    int result = 0;
                    for (int i = 0; (i < nChildren1) && (result == 0); i++) {
                        compare(n1.children.get(i), n2.children.get(i));
                    }
                    return result;
                } else {
                    /*- If one node has more children than the other, sort accordingly */
                    return ((nChildren1 > nChildren2) ? 1 : -1);
                }
            }
        }
    }

    static void sortForest(Node root) {
        for (int i = 0; i < root.children.size(); i++) {
            sortForest(root.children.get(i));
            root.children.sort(comp);
        }
        return;
    }

Question

How can one get this code to work? I'm somewhat sure this is roughly in the ballpark of a correct solution, but I've tried to think this through over several hours now and can't figure out one. I'm convinced that this is giving me stack-overflows due to a never-ending recursion being in there somewhere, I just don't see it. The recursion in general is giving me problems to properly do this mentally. I couldn't find identical questions to this and those that were similar concerned themselves with binary trees instead of unordered ones.

Answer 1

Depending on the tree's size you might run into limitations when calling sortForest regarding Java's default stack size. Ways around it include increasing it via the -Xss JVM option, setting the stack size in the Thread constructor, re-writing it non-recursive or using the Trampoline pattern.

Answer 2

There are several things wrong with the above code:

1. The code assumed that the root node of each tree did not contain a reference to itself (not shown in the code above), which originally caused the compare method to call the root again and again, this was rectified.

2. It is absolutely unnecessary and actually wrong to call for sorting in the comparison method. The code is already calling for sort methods for every Node with sortForest(), starting from the leaves, so that has no place there and needs to be removed from all parts of the code of the compare method.

3. With the given return the compare method does not lead to a sort from largest to smallest, but from smallest to largest. It needs to return 1 where it returns -1 and vice versa.

4. The compare method also needs, in its for loop, to store the return of compare() in result, otherwise result never changes and the loop doesn't stop once a dis-similarity has been found.

5. The sorting with root.children.sort(comp); in sortForest() absolutely must happen outside of the forLoop, otherwise you sort some of the ArrayList while you still need them in their original order to perform all the calls correctly.

After rectifying all of these, the sortForest() and compare() methods above delivered the correct sorting results for example trees like:

int[] tree1 = { 2, 3, 3, 3, 2, 2, 1, 0, 7, 5, 3, 10, 10, 6 };

int[] tree2 = { 4, 10, 11, 0, 4, 0, 12, 4, 7, 8, 0, 3, 4, 12 };

And sort them as shown in this picture.

The full code of the solution together with some optimizations and removal of unnecessary code and with fixed sorting can be found here