2
\$\begingroup\$

Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped.

  1. Looking for code-review, optimizations and best practices
  2. This class appears to be threadsafe. Am I correct ?
  3. Verifying - Complexity appears to be O(n), where n is number of nodes of larger tree.

public final class IsomorphicChecker<T> {

    private TreeNode<T> root;

    /**
    * Constructs a binary tree in order of elements in an array.
    * The input list is treated as  BFS representation of the list.
    * Note that it is the clients reponsibility to not modify input list in objects lifetime.
    */
    IsomorphicChecker(List<T> items) {
        create(items);
    }

    private void create(List<? extends T> items) {
        root = new TreeNode<T>(null, items.get(0), null);

        final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNode<T> current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNode<T>(null, items.get(left), null);
                    queue.add(current.left);
                }
                if (right < items.size() && items.get(right) != null) {
                    current.right = new TreeNode<T>(null, items.get(right), null);
                    queue.add(current.right);
                }
            }
        }
    }

    private static class TreeNode<T> {
        TreeNode<T> left;
        T item;
        TreeNode<T> right;

        TreeNode(TreeNode<T> left, T item, TreeNode<T> right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

    /**
     * Checks if trees are isomorphic
     * 
     * @param tree      the input tree 
     * @return          true if input tree is isomorphic to current tree
     */
    public boolean checkIsomortphic(IsomorphicChecker<T> tree) {
        return checker(root, tree.root);
    }

    private boolean checker(TreeNode<T> node1, TreeNode<T> node2) {
        if (node1 == null && node2 == null) {
            return true;
        }

        if (node1 == null || node2 == null) {
            return false;
        }

        if (!node1.item.equals(node2.item)) {
            return false;
        }

        return  checker(node1.left, node2.left) && checker(node1.right, node2.right) || 
                    checker(node1.left, node2.right) && checker(node1.right, node2.left);
    }

    public static void main(String[] args) {
        IsomorphicChecker<Integer> nonRecursiveTraversal1 = new IsomorphicChecker<Integer>(Arrays.asList(1, 2, 3));
        IsomorphicChecker<Integer> nonRecursiveTraversal2 = new IsomorphicChecker<Integer>(Arrays.asList(1, 2, 3));
        IsomorphicChecker<Integer> nonRecursiveTraversal3 = new IsomorphicChecker<Integer>(Arrays.asList(1, 3, 2));

        assertTrue(nonRecursiveTraversal1.checkIsomortphic(nonRecursiveTraversal2));
        assertTrue(nonRecursiveTraversal1.checkIsomortphic(nonRecursiveTraversal3));

        IsomorphicChecker<Integer> nonRecursiveTraversal4 = new IsomorphicChecker<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, null, null, null, 7, 8, null, null, null, null));
        IsomorphicChecker<Integer> nonRecursiveTraversal5 = new IsomorphicChecker<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, null, null, null, 7, 8, null, null, null, null));
        IsomorphicChecker<Integer> nonRecursiveTraversal6 = new IsomorphicChecker<Integer>(Arrays.asList(1, 3, 2, null, 6, 4, 5, null, null, null, null, null, null, 8, 7));

        assertTrue(nonRecursiveTraversal4.checkIsomortphic(nonRecursiveTraversal5));
        assertTrue(nonRecursiveTraversal4.checkIsomortphic(nonRecursiveTraversal6));


        assertFalse(nonRecursiveTraversal4.checkIsomortphic(nonRecursiveTraversal1));
    }
}
\$\endgroup\$
2
\$\begingroup\$

As a general comment, your code has improved significantly in the last few months. It is to your benefit for multiple reasons.... the 'easy' things to review have gone (code style, variable names, etc.) and the core logic is much more readable. Reviewing your work is harder now because the easy things are all done right.

TreeNode

  • final item:

    T item

    should be final.

  • Even though it is an internal class, you should still have getters/setters for left, right, and item. This makes it more readable in the code instead of having chained field names.... for example:

    if (!node1.item.equals(node2.item)) {
    

    should be:

    if (!node1.getItem().equals(node2.getItem())) {
    

    Speaking of which ... do you intend to support null items?

    Another issue with not having the getters, is the confusion with code like:

    current.left = new TreeNode<T>(null, items.get(left), null);
    

    On that line, current.left is a TreeNode, but the left in items.get(left) is an integer. it would be better as:

    current.setLeft(new TreeNode<T>(null, items.get(left), null));
    

checkIsoMorphic(...)

  • should be spelled correctly ;-)

Checker

  • you should consider using the new-to-Java7 Objects.equals(a,b) methods instead of your own. To do that, you should implement the equals() and hashCode() methods on TreeNode

Complexity

It is O(n), but where n is the size of the smaller tree, not the larger tree.

Concurrency

This is a complicated question. But, basically, no, it is not.

If you assume that the core tree is static for the lifetime of the IsomorphicChecker instance, and that the test teee is static for the lifetime of the checkIsomorphic, then, the code can be considered reentrant.

But, even though you say "Note that it is the clients reponsibility to not modify input list in objects lifetime.", that comment does not make the code thread-safe.

\$\endgroup\$
  • \$\begingroup\$ Firstly I thank you and community to help me grow, but I had some comments - 1. final item : the reason for not making this final is because in general a collections say entry in linkedlist can be subject to changed value. Although this code does not change it, I still dont want to "force" to not change it. 2. About getters/setters: I just followed Linkedlist.java of Sun, and code was of internal Node. They did not add getter/setters as it was private and internal and it would be in my opinion an overkill. 3. I agree with complexity. its the smaller tree. 4. Interesting insight on concurrency \$\endgroup\$ – JavaDeveloper Apr 3 '14 at 1:15
0
\$\begingroup\$

A minor bug: You get an IndexOutOfBoundsException for an empty list in IsomorphicChecker.create(List<? extends T> items). You don't have a comment stating you need to input a list containing at least something. Consider returning IllegalArgumentException and adding a comment.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.