Find if a tree is a mirror of itself

Find if a tree is a mirror of itself. You can consider the tree to be a binary tree

Approach1 : Tree will be a palindrome at each level. Do a level order traversal and check for palindrome and break

Approach2 : Use a variant of recursive function for checking sameTree() instead of checking left and left, right and right. Check left with right and right with left.

Code using palindrome approach

------------------------------------------

import java.util.ArrayList;

import java.util.List;

public class BFS {

    List nodeList = new ArrayList();
    List nodeList1 = new ArrayList();
    List list, list1;

    public boolean isSymmetricTree(Node n) {
        // do a BFS traversal of this tree
        if (n == null) {
            //null is symmetric
            return true;
        }
        if ( n != null && n.left == null && n.right == null ) {
            // only 1 node;
            return true;
        }
        nodeList.add(n.left);
        nodeList.add(n.right);

        list = nodeList;
        list1 = nodeList1;
        while (list.size() > 0) {
            int count = 0;
            while (count < list.size()) {
                //System.out.println("Count = " + count + " list.size = " + list.size());
                Node tempNode = (Node)list.get(count);
                if (tempNode != null) {
                    //store it's left right
                    if (tempNode.getLeft() != null)
                        list1.add(tempNode.left);
                    if (tempNode.getRight() != null)
                        list1.add(tempNode.right);
                }
                count++;
            }
            if (isPalindrome(list) == false) {
                return false;
            }
            emptyList(list);
            List tmp = list;
            list = list1;
            list1 = tmp;
        }
        return true;
    }

   

    private static void emptyList(List nodeList) {
        if (nodeList != null)
            nodeList.clear();
    }
   
  private static void printArray(Node[] nodes) {
        for (int i =0; i < nodes.length; i++) {
            System.out.println ( i + " th Node = [ " + nodes[i].getData() + "]");
        }
    }

    private boolean isPalindrome(List nodeList) {
        if (nodeList == null || nodeList.size() == 0 )
            return true;
        Node[] nodes = new Node[nodeList.size()];
        nodeList.toArray(nodes);
        //printArray(nodes);
        //for it to be symmetric nodes.length should be an even number
        if (nodes.length % 2 != 0)
            {
                System.out.println("List size is not symmetric ..returning false");
                return false;
            }
        int start = 0;
        int end = nodes.length - 1;
        while ( start < end) {
            //System.out.println("Comparing " + nodes[start].getData()  + nodes[start].getData());
            if (nodes[start].getData() == nodes[end].getData())  {
                start++;
                end--;
            }
            else
                {
                    //System.out.println("Comparing " + nodes[start].getData()  +  " " + nodes[start].getData() + " and returning false");
                    return false;
                }
        }
        //System.out.println (" isPalindrome function returning true");
        return true;
    }

}

public class Node {

    Long data;

    Node left;

    Node right;

    public Node() {

    }

   

    public Node(Long data) {

        this.data = data;

    }

    public Long getData() {

        return data;

    }

    public void setData(Long data) {

        this.data = data;

    }

    public Node getLeft() {

        return left;

    }

    public void setLeft(Node left) {

        this.left = left;

    }

    public Node getRight() {

        return right;

    }

    public void setRight(Node right) {

        this.right = right;

    }

   

   

}

public class TreeTest {

    public static void main(String[] args) {

        /* Test case 1 what we discussed over the phone */

       

        Node n =  FileUtils.constructTree();

        BFS bfs = new BFS();

        if (bfs.isSymmetricTree(n))

            {

                System.out.println("------Tree is symmetric------");

            }

        else {

            System.out.println("-----Tree is asymmertric-------");

        }

        System.out.println(" ");System.out.println(" ");System.out.println(" ");

        System.out.println("=============Second positive test case===============");

        n = new Node(1L);

        Node n1 = new Node(2L);

        Node n2 = new Node(2L);

        Node n3 = new Node(4L);

        Node n4 = new Node(4L);

        n4.setLeft(null);

        n4.setRight(null);

        n3.setLeft(null);

        n3.setRight(null);

        n2.setLeft(null);

        n2.setRight(n4);

        n1.setLeft(n3);

        n1.setRight(null);

        n.setLeft(n1);

        n.setRight(n2);

        if (bfs.isSymmetricTree(n))

            {

                System.out.println("------Tree is symmetric-------");

            }

        else {

            System.out.println("------Tree is asymmertric------");

        }

        System.out.println(" ");System.out.println(" ");System.out.println(" ");

       

        System.out.println("=============Third negative test case===============");

        n = new Node(1L);

        n1 = new Node(2L);

        n2 = new Node(2L);

        n3 = new Node(4L);

        n4 = new Node(5L);

        n4.setLeft(null);

        n4.setRight(null);

        n3.setLeft(null);

        n3.setRight(null);

        n2.setLeft(null);

        n2.setRight(n4);

        n1.setLeft(n3);

        n1.setRight(null);

        n.setLeft(n1);

        n.setRight(n2);

 if (bfs.isSymmetricTree(n))

            {

                System.out.println("Tree is symmetric");

            }

        else {

            System.out.println("------Tree is asymmertric------");

        }

   

}

   

}


Code using recursive Approach mentioned in Comment1
---------------------------------------------------------------------

public class TreeOps {

    class Node {
    int data;
    Node left;
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    Node right;
   
    }
    public boolean isSymmetricTree(Node root) {
        if (root == null)
            return true;
        if (root.getLeft() == null && root.getRight() == null)
            return true;
        return isSymmetricTree(root.left, root.right);
    }
   
    private boolean isSymmetricTree(Node left, Node right) {
        if (left == null && right == null) {
            return true;
        }
        if ((left == null && right != null) ||
                (left != null && right == null))
            return false;

        return left.getData() == right.getData() &&
        isSymmetricTree(left.getLeft(), right.getRight()) &&
        isSymmetricTree(left.getRight(), right.getLeft());
       
    }
   
    public void testIsSymmetricTreePositiveOne() {
    Node n = new Node();
    Node n1 = new Node();
    Node n2 = new Node();
    Node n3 = new Node();
    Node n4 = new Node();
    n.setData(1);
    n1.setData(2);
    n2.setData(2);
    n3.setData(3);
    n4.setData(3);
    n.setLeft(n1);
    n.setRight(n2);
    n1.setLeft(n3);
    n1.setRight(null);
    n2.setRight(n4);
    n2.setLeft(null);
    System.out.println("testIsSymmetricTreePositiveOne  = [" +isSymmetricTree(n) + "]");
   
   
    }
   
    public void testIsSymmetricTreePositiveTwo() {
        Node n = new Node();
        Node n1 = new Node();
        Node n2 = new Node();
        Node n3 = new Node();
        Node n4 = new Node();
        Node n5 = new Node();
        Node n6 = new Node();
        n.setData(1);
        n1.setData(2);
        n2.setData(2);
        n3.setData(3);
        n4.setData(3);
        n5.setData(4);
        n6.setData(4);
        n.setLeft(n1);
        n.setRight(n2);
        n1.setLeft(n3);
        n1.setRight(n5);
        n2.setRight(n4);
        n2.setLeft(n6);
        System.out.println("testIsSymmetricTreePositiveTwo  = [" +isSymmetricTree(n) + "]");
       
        }
   
    public void testIsSymmetricTreeNegativeOne() {
        Node n = new Node();
        Node n1 = new Node();
        Node n2 = new Node();
        Node n3 = new Node();
        Node n4 = new Node();
        Node n5 = new Node();
        n.setData(1);
        n1.setData(2);
        n2.setData(2);
        n3.setData(3);
        n4.setData(3);
        n5.setData(4);
        n.setLeft(n1);
        n.setRight(n2);
        n1.setLeft(n3);
        n1.setRight(n5);
        n2.setRight(n4);
        System.out.println("testIsSymmetricTreeNegativeOne  = [" +isSymmetricTree(n) + "]");
       
        }
    public static void main(String[] args) {
        TreeOps t = new TreeOps();
        t.testIsSymmetricTreePositiveOne();
        t.testIsSymmetricTreePositiveTwo();
        t.testIsSymmetricTreeNegativeOne();
    }
   
   
}