Compare 2 unordered, rooted trees for shape-isomorphism

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.

Edit: This question now also has a follow-up question here.

Translation of the exercise

Write a program to check if 2 int arrays of N whole numbers between 0 and N-1 represent 2 isomorphic unordered trees, if you interpret the arrays as predecessor-successor-connections in a tree (e.g. in an int array index 3 has value 5. That means the node with value 3 is child of the node with value 5) , while the nodes are numbered from 0 to N-1. That means, your program should determine if there is a way to re-number the nodes in a tree, so that the array-representation of one tree is identical to the array-representation of the other tree.

My interpretation

Since we are talking about unordered, rooted trees whose order of nodes does not matter, I think this exercise asks also if the nodes of one unordered tree can be rearranged (while keeping general connectivity between nodes intact) in such a way that it is shape-isomorphic to the other. As such, unordered trees that at first glance don't seem to be shape-isomorphic might still be, that needs to be accounted for.

(Question on the side: Does this qualify for the programming-challenge-tag?)

My Algorithm

1. Recreate the trees from the array using Node objects. Each node object contains its value called value and an ArrayList of node references called children

2. Sort the nodes in the unordered trees according to the amount of children, further called nChildren , they have directly connected to them. Sort left to right in descending order. Go from left to right, start sorting at the leaves and work your way up. If 2 sibling-nodes n1 and n2 have identical nChildren, compare the nChildren of their children from largest to lowest. If no difference is found, compare the the nChildrenof their children, again from largest to lowest. Repeat until difference is found or you find that these already sorted sub-trees that have n1 and n2 as roots have shape-isomorphism. In that case their order is irrelevant.

(2 Examples for the sorting can be found at the end of the post).

4. Compare the two now sorted trees and check for shape-isomorphism. Go recursively through the two trees in post-Order. Possible Cases: 1) Both currently observed nodes are leaves 2) The two observed nodes have unequal nChildren (e.g. one is a leaf while the other isn't) 3) Both observed nodes have equal nChildren. 1) and 2) are the base cases. If at any point one method call returns false, return false for all calls that lead to calling this iteration of the method. Else return true.

The code

WARNING: The below code contains 3 bugs (1 in "sortForest()", 1 in "compareTrees", 1 in "compare", all of which have been mentioned and corrected in my answer to this question.

package Kapitel5;

import java.util.ArrayList;
import java.util.Comparator;

public class Test {
    static final 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: Both Nodes have unequal amounts of nodes 
             * -> return (-) 1
             */
            if (n1.children.isEmpty() && n2.children.isEmpty()) {// BaseCase1
                return 0;
            } else if (n1.children.size() != n2.children.size()) {// BaseCase2
                return ((n1.children.size() > n2.children.size()) ? -1 : 1);
            } else {
                /*
                 * If n1 and n2 have equal amounts of children, compare the
                 * amounts of children their children have, from largest to
                 * lowest. If the default assumption is ever wrong, do not
                 * perform further comparisons
                 */
                int result = 0; /*- Default assumption - Sub-trees of n1 and n2 are equal*/
                for (int i = 0; (i < n1.children.size()) && (result == 0); i++) {
                    compare(n1.children.get(i), n2.children.get(i));
                }
                return result;
            }
        }
    }

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

    static void removeRootFromChildren(Node root) {
        int i = 0;
        while (root.children.get(i) != root) {
            i++;
        }
        root.children.remove(i);
    }

    static Node createTreeFromArray(int[] tree) {
        Node[] treeNodes = new Node[tree.length];
        for (int i = 0; i < tree.length; i++) {
            treeNodes[i] = new Node(i, new ArrayList<Node>(15));
        }
        Node root = null;
        /*-Fill the ArrayLists of each Node with references to their child-Nodes*/
        for (int i = 0; i < tree.length; i++) {
            treeNodes[tree[i]].children.add(treeNodes[i]);
            if (tree[i] == i) {
                root = treeNodes[i];
            }
        }
        /* Ascertain that tree has root */
        if (root == null) {
            throw new RuntimeException("Given tree-array has no root!");
        } else {
            removeRootFromChildren(root);
            return root;
        }
    }

    static boolean compareTrees(Node nodeFromTree1, Node nodeFromTree2) {
        /*-
         * BaseCase1: Both nodes are leaves -> return true 
         * BaseCase2: Both nodes have unequal amounts of children -> return false
         */
        if (nodeFromTree1.children.isEmpty() && nodeFromTree2.children.isEmpty()) {
            return true;
        } else if (nodeFromTree1.children.size() != nodeFromTree2.children.size()) {
            return false;
        } else {
            boolean treesAreIsomorph = true; // Default Assumption
            for (int i = 0; i < nodeFromTree1.children.size(); i++) {
                treesAreIsomorph = compareTrees(nodeFromTree1.children.get(i), nodeFromTree2.children.get(i));
            }
            return treesAreIsomorph;
        }
    }

    public static void main(String[] args) throws Exception {
        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 };

        Node root1 = createTreeFromArray(tree1);
        Node root2 = createTreeFromArray(tree2);

        sortForest(root1);
        sortForest(root2);

        System.out.println(compareTrees(root1, root2));

    }
}

Questions

1. Should I have avoided the static NodeComparator variable? I used it since, in the end, it saved me a lot of instantiating of an object to pass to ArrayLists sort() method. I don't know as of now how to do the sorting with the provided sort() without passing an object.

2. Could I have reduced the BaseCases down from 2 to 1 in both recursive methods? I couldn't think of a way to do it.

3. Was the algorithm I thought of acceptable or should I have gone for a different approach? If yes, please explain which one, this was the only one I could think of.

I'd appreciate it if reviews of the code itself focused especially on the recursive methods, since I think that's the part where I'm struggling the most.

Examples for the sorting

2 examples for the sorting of the trees:

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

Answer 1

It looks like you have a small bug on your compare function. You don't change result, if compare returns anything. This means your else always returns 0.

Your leaf stuff is also not needed, as if you're comparing a leaf to a non-leaf it'll be caught by the else if, and if you're comparing a leaf with a leaf, the for loop will never run.

public int compare(Node n1, Node n2) {
    if (n1.children.size() != n2.children.size()) {
        return ((n1.children.size() > n2.children.size()) ? -1 : 1);
    }
    int result = 0;
    for (int i = 0; (i < n1.children.size()) && (result == 0); i++) {
        result = compare(n1.children.get(i), n2.children.get(i));
    }
    return result;
}

Answer 2

The code given above is buggy and non-functional, which I did not notice until Peilonrayz pointed it out.

Another bug is that "sortForest()" invokes the sort method of the ArrayList inside the forLoop, leading to incorrect sorting that doesn't throw an error. That should look like the following:

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

An additional bug is that compareTrees() does not stop comparing once a difference is found. It needs to include "treesAreIsomorph" in its conditions to check in the forLoop.

static boolean compareTrees(Node nodeFromTree1, Node nodeFromTree2) {
    if (nodeFromTree1.children.size() != nodeFromTree2.children.size()) {
        return false;
    } else {
        boolean treesAreIsomorph = true; // Default Assumption
        for (int i = 0; i < nodeFromTree1.children.size() && treesAreIsomorph; i++) {
            treesAreIsomorph = compareTrees(nodeFromTree1.children.get(i), nodeFromTree2.children.get(i));
        }
        return treesAreIsomorph;
    }
}

Those are on top of the bug that Peilonrayz already found, whose correct version is:

public int compare(Node n1, Node n2) {
            if (n1.children.size() != n2.children.size()) {
                return ((n1.children.size() > n2.children.size()) ? -1 : 1);
            } else {
                int result = 0; /*- Default assumption - Sub-trees of n1 and n2 are equal*/
                for (int i = 0; (i < n1.children.size()) && (result == 0); i++) {
                    result = compare(n1.children.get(i), n2.children.get(i));
                }
                return result;
            }
        }
    }