Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

To solve it recursively is easy.

01 public boolean isSymmetric(TreeNode root) {

02     if(root==null)

03         return true;      

04     return isMirror(root.left,root.right);

05 }

06 

07 public boolean isMirror(TreeNode t1, TreeNode t2)

08 {

09     if(t1==null)

10     {

11         if(t2==null)

12             return true;

13         else

14             return false;

15     }

16     if(t2==null && t1!=null)

17         return false;

18     if(t1.val==t2.val)

19     {

20         return isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);

21     }

22     else

23         return false;

24 }

To solve it without recursion, we should use BFS, with the help of a queue structure. As there is no depth field of each node, we should use an additional queue to keep track of the levels of nodes.

01 public boolean isSymmetric(TreeNode root) {
02     if(root==null)
03         return true;
04   
05     ArrayList<TreeNode> trees=new ArrayList<TreeNode>();
06     ArrayList<Integer> depth=new ArrayList<Integer>();
07     trees.add(root);
08     depth.add(1);
09     while(!trees.isEmpty())
10     {
11         TreeNode parent=trees.remove(0);
12         int curr_depth=depth.remove(0);
13         if(parent!=null)
14         {
15             trees.add(parent.left);
16             depth.add(curr_depth+1);          
17             trees.add(parent.right);
18             depth.add(curr_depth+1);
19         }
20       
21       
22         int size=depth.size();
23       
24         if( !depth.isEmpty() && curr_depth==depth.get(0)-1 && depth.get(0)==depth.get(size-1) )
25         {
26             int i=0;
27             int j=size-1;
28           
29             while(i<j)
30             {
31                 if(trees.get(i)==null)
32                 {
33                     if(trees.get(j)==null)
34                     {
35                         i++;
36                         j--;
37                     }
38                     else
39                         return false;
40                 }
41                 else if(trees.get(i)!=null && trees.get(j)==null)
42                 {
43                     return false;
44                 }                  
45                 else if(trees.get(i).val==trees.get(j).val)
46                 {
47                     i++;
48                     j--;
49                 }
50                 else
51                 {
52                     return false;
53                 }
54               
55             }
56 
57         }
58       
59     }
60   
61     return true;
62 }