[closed] Same Tree

class Solution {

public:

  bool checkSub(TreeNode *p, TreeNode *q) {
      if(p == NULL && q == NULL) return true;
      if(p == NULL || q == NULL) return false;
      if(p->val == q->val && checkSub(p->left, q->left) && checkSub(p->right, q->right))
          return true;
      return false;
  }
  bool isSameTree(TreeNode *p, TreeNode *q) {
      return checkSub(p, q);
  }
};

class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
    if(!p && !q)
        return true;
    if (p && q)
    {
        if(p->val == q->val)
            return (isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
        else
            return false;
    }
    else
        return false;   
 }
};

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(p==null&&q==null) return true;
        if(p==null||q==null) return false;
        if(p.val!=q.val) return false;
        boolean left=isSameTree(p.left,q.left);
        if(!left) return left;
        boolean right=isSameTree(p.right,q.right);
        return right;
    }
}

class Solution 
{
public:
bool isSameTree(TreeNode *p, TreeNode *q) 
  {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if( !p && !q) return true;
    if( p && q && (p->val  == q->val)) return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    else 
        return false;
  }
};

bool isSameTree(TreeNode *p, TreeNode *q) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(p==NULL && q==NULL) return true;
    else if(p != NULL && q != NULL){
        return (p->val == q->val &&
                isSameTree(p->left, q->left) &&
                isSameTree(p->right, q->right));
    }
    else return false;
}

bool isSameTree(TreeNode p, TreeNode q) {

    if(!p && !q) return true;
    if(!p || !q) return false;
    if(p->val==q->val) return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    else return false;

}

Following is the O(min(m, n)) Solution where m = number of nodes in tree1 and n = number of nodes in tree2.

The recursion uses the implicit stack. In order to implement it iteratively we need to use in-order traversal logic.

following is the code.

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (p == NULL && q == NULL)
            return true;
        if (p == NULL && q != NULL)
            return false;
        else if (p != NULL && q == NULL)
            return false;
        else if (p->val != q->val)
            return false;
        else
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

    }
};

public boolean isSameTree(TreeNode p, TreeNode q) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if(p==null && q==null)
        return true;
    else if(p==null || q==null)
        return false;
    else if(p.val!=q.val)
        return false;
    else
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

boolean sameTree(Node node1, Node node2)
{
    //base case
    if (node1 == null && node2==null)
    {
        return true;
    }
    else if ((node1 == null && node2 != null) || (node1 != null && node2 == null))
    {
        return false;
    }

    //now node1 != null && node2 != null
    if (node1.data != node2.data)
    {
        return false;
    }

   //node1.data == node2.data

   boolean leftEqual = sameTree(node1.leftChild, node2.leftChild);
   boolean rightEqual = sameTree(node1.rightChild, node2.rightChild);

   return leftEqual && rightEqual;
}