Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Naive Way: The question is not difficult. Write both iterative and recursive methods.

Recursive Method.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     // base case  
     if(p==null || q==null) return p==null && q==null;  
     // recursion  
     return p.val==q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);  
   }  
 }  

Iterative Method.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     // edge case  
     if(p==null || q==null) return p==null && q==null;  
     // general case, BFS  
     Queue<TreeNode> p_queue = new LinkedList<TreeNode>();  
     Queue<TreeNode> q_queue = new LinkedList<TreeNode>();  
     p_queue.offer(p);  
     q_queue.offer(q);  
     while(!p_queue.isEmpty() && !q_queue.isEmpty()){  
       TreeNode p_node = p_queue.poll();  
       TreeNode q_node = q_queue.poll();  
       if(p_node.val!=q_node.val) return false;  
       if(p_node.left!= null && q_node.left!=null){  
         p_queue.offer(p_node.left);  
         q_queue.offer(q_node.left);  
       }else if(!(p_node.left==null && q_node.left==null))  
         return false;  
       if(p_node.right!= null && q_node.right!=null){  
         p_queue.offer(p_node.right);  
         q_queue.offer(q_node.right);  
       }else if(!(p_node.right==null && q_node.right==null))  
         return false;  
     }  
     return p_queue.isEmpty() && q_queue.isEmpty();  
   }  
 }