The previous post can be found here.

In the previous post I tried to solve an exercise but found through the answer of Peilonrayz a bug in the code and 2 more while fixing it. These have now been amended (changes to the original code can be seen in my answer in the previous question).

The exercise (Copy&Paste from the previous question)

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.

Sidenote: I interpreted this as: "Check for tree-isomorphism between 2 trees given in int arrays". I believe this also means that one needs to check if one tree can be re-arranged in any fashion, so that shape-isomorphism occurs.

The Algorithm (Copy&Paste from the previous question)

  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.

  3. 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.

(2 Examples for the sorting can be found in the previous question).

The code

package Kapitel5;

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

public class Test {
    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) {
            /*-
             * Case1: Both Nodes have unequal amounts of nodes 
             * -> return (-) 1
             * Case2: Both Nodes have equal amounts of nodes 
             * -> test child-nodes or return 0 if that is impossible;
             */
            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++) {
                    result = compare(n1.children.get(i), n2.children.get(i));
                }
                return result;
            }
        }
    }

    static final NodeComparator comp = new NodeComparator();

    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 {
            /*
             * Trees are given in format where roots point at themselves and are
             * therefore listed as children in their own ArrayList. Remove it.
             */
            removeRootFromChildren(root);
            return root;
        }
    }

    static boolean compareTrees(Node nodeFromTree1, Node nodeFromTree2) {
        /*-
         * Case1: Both Nodes have unequal amounts of nodes 
         * -> return false;
         * Case2: Both Nodes have equal amounts of nodes 
         * -> test child-nodes or return true if that is impossible;
         */
        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;
        }
    }

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

The given trees in the code should and do return "true" when given to compareTrees().

Questions (Copy&Paste from the previous question)

Question No. 2 got solved in the previous post.

  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. [...]
  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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.