# Symmetric Tree – recursion and iteration

This is No.101 problem in leetcode.

The question is:

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

1.Recursion:

• Recursion occurs when a thing is defined in terms of itself or of its type.

• In this problem, I will solve it in recursion first.

• The thought is staright, I need to check if root given exists, if not, then return true(because empty tree is symmetric), if does, then I will call recursion function to process the rest of this problem.

• The second part is the main part of this problem. And I make a mistake here. I thought that recursion function must be same as "itself", so I took some time to consider how to use only one parameter to solve it. But I was worng, I can use a same name function with two parameters, so from the last step, I passed the left child and right child of root to my new recursion function.

• Inside this function, I check if both of child exists, if not then return true. After I make sure that not both of them are null, then I check if one of them are null, if so then return false.

• After that, I check if the value are same, if not then return false.

• At last, I call recursion function to check the left of left with the right of right and the right of left with the left of right.

• My code is below:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
// base case
if(root == null){
return true;
}
//System.out.println("pass1");
// use recursion
return isSymmetric( root.left, root.right);
}

public boolean isSymmetric(TreeNode lr, TreeNode rr){
// first we check if exist
// if they don't exist, then true
if(lr == null && rr == null){
return true;
}
//System.out.println("pass2");
// if only on exists, then false
if(lr == null || rr == null){
return false;
}
//System.out.println("pass3");
// then we check if value same
if(lr.val != rr.val ){
return false;
}
//System.out.println("pass4");
// then check the child of root;
return isSymmetric(lr.left, rr.right) && isSymmetric(lr.right, rr.left);
}
}``````
1. Iteration
• Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes.

• In iteration, the thought is to build two queues which will be inserted each pair of child from right and left root and compare. I complete the code but it is time limit exceeded.

• My code is below:

``````
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {

// base case
if(root == null){
return true;
}

// build two queue

Queue lq = new LinkedList();
Queue rq = new LinkedList();

// add right and left child to queue
lq.offer(root.left);
rq.offer(root.right);

// loop to make sure element exists
while(!lq.isEmpty() && !rq.isEmpty()){
// get two node
TreeNode ln = lq.peek();
TreeNode rn = rq.peek();
// check if value same
if(ln.val != rn.val){
return false;
}
// add new pair
lq.offer(ln.left);
lq.offer(ln.right);
rq.offer(rn.right);
rq.offer(rn.left);
}

// check if any elements exist
if(!lq.isEmpty() || !rq.isEmpty()){
return false;
}

return true;
}``````