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);
    }
}

2. 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;
  }