Bug in code for finding if a tree is symmetric or not

Question

I have written a code to check if a tree is symmetric (A tree is symmetric if it is a mirror image of itself) or not. Let's say, we are given a tree A. Here, I am trying to create a new tree B using the function mirror() which is a mirror image of tree A. When I am printing the tree B in main function, it is correctly printing the mirror image. But, when the same mirror function is being called inside the function isSymmetric(), it returns the original tree itself. Other solutions are already available on different platforms. I just want to know why my code behaves differently when the same function is called at different places.

import java.util.*;

class BinaryTree { Node root;

BinaryTree(int d) {
    root = new Node(d);
}

BinaryTree() {
    root = null;
}

static class Node {//why static is needed ?
    int data;
    Node left, right;

    Node(int d) {
        data = d;
        left = null;
        right = null;
    }
}

boolean isSymmetric(Node root) {
    if(root == null)
        return true;
    if(root.left == null && root.right == null)
        return true;
    Node root2 = mirror(root);
    printTree(root);
    System.out.println();
    printTree(root2);//this should print mirror image of tree but it is printing the original tree 
    return isMirror(root, root2);
}

Node mirror(Node root) {
    if(root == null)
        return root;
    if(root.left == null && root.right == null) {
        return root;
    }
    Node left = mirror(root.left);
    Node right = mirror(root.right);
    root.left = right;
    root.right = left;
    return root;
}

boolean isMirror(Node n1, Node n2) {
    if(n1 == null && n2 == null)
        return true;
    if(n1 == null || n2 == null)
        return false;
    if(n1.data != n2.data)
        return false;
    return isMirror(n1.left, n2.left) && isMirror(n1.right, n2.right);
}

void printTree(Node root) {
    Queue q = new LinkedList();
    if(root != null) {
        q.add(root);
    }
    else {
        System.out.println("empty tree");
    }
    while(!q.isEmpty()) {
        Node y = q.remove();
        System.out.print(y.data + " ");
        if(y.left != null)
            q.add(y.left);
        if(y.right != null)
            q.add(y.right);
    }
}

public static void main (String[] args) throws java.lang.Exception
{
    // your code goes here
    BinaryTree t = new BinaryTree(5);
    t.root.left = new Node(6);
    t.root.right = new Node(4);
    t.root.left.left = new Node(7);
    t.root.left.right = new Node(8);
    t.root.right.left = new Node(9);
    t.root.right.right = new Node(10);
    t.printTree(t.root);
    t.root = t.mirror(t.root);
    System.out.println();
    t.printTree(t.root);
    System.out.println();
    System.out.print(t.isSymmetric(t.root));
}

}

Hadi Moloodi · Accepted Answer

The main reason is you are calling mirror method two times on the same root. the second call reverses the effect of the first call.

you can change your code to achieve your result like this, there was a mistake in your isMirror function which I fixed.

public class BinaryTree {
    Node root;

    BinaryTree(int d) {
        root = new Node(d);
    }

    BinaryTree() {
        root = null;
    }

    public static void main(String[] args) throws java.lang.Exception {
        // your code goes here
        BinaryTree t = new BinaryTree(5);
        t.root.left = new Node(6);
        t.root.right = new Node(4);
        t.root.left.left = new Node(7);
        t.root.left.right = new Node(8);
        t.root.right.left = new Node(9);
        t.root.right.right = new Node(10);
        t.printTree(t.root);
        Node MirroredNode = t.mirror(t.root.clone());
        System.out.println();
        t.printTree(t.root);
        t.printTree(MirroredNode);
        System.out.println();
        System.out.print(t.isSymmetric(t.root));
    }

    boolean isSymmetric(Node root) {
        if (root == null)
            return true;
        if (root.left == null && root.right == null)
            return true;
        Node root2 = mirror(root.clone());
        printTree(root);
        System.out.println();
        printTree(root2);//this should print mirror image of tree but it is printing the original tree
        return isMirror(root, root2);
    }

    Node mirror(Node root) {
        if (root == null)
            return root;
        if (root.left == null && root.right == null) {
            return root;
        }
        Node left = mirror(root.left.clone());
        Node right = mirror(root.right.clone());
        root.left = right;
        root.right = left;
        return root;
    }

    boolean isMirror(Node n1, Node n2) {
        if (n1 == null && n2 == null)
            return true;
        if (n1 == null || n2 == null)
            return false;
        if (n1.data != n2.data)
            return false;
        return isMirror(n1.left, n2.right) && isMirror(n1.right, n2.left);
    }

    void printTree(Node root) {
        Queue q = new LinkedList();
        if (root != null) {
            q.add(root);
        } else {
            System.out.println("empty tree");
        }
        while (!q.isEmpty()) {
            Node y = q.remove();
            System.out.print(y.data + " ");
            if (y.left != null)
                q.add(y.left);
            if (y.right != null)
                q.add(y.right);
        }
    }

    static class Node implements Cloneable {//why static is needed ?
        int data;
        Node left, right;

        Node(int d) {
            data = d;
            left = null;
            right = null;
        }

        @Override
        public Node clone() {
            try {
                return (Node) super.clone();
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
            return null;
        }
    }
}

Bug in code for finding if a tree is symmetric or not

Answers (2)

Related Questions