Checking if two binary trees are identical

Question

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Tree is defined as :

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

And my solution is

public boolean isSameTree(TreeNode p, TreeNode q) {
 if(null == p && null == q){
 return true;
 }
 if((null == p && null != q) || (null == q && null != p)){
 return false;
 }
 if(p.val == q.val){
 return isSameTree(p.left,q.left) ? isSameTree(p.right,q.right) :false;
 } else {
 return false;
 }
}

Please suggest any improvements.

Answer 1

Your code already does its job well. It can be shortened a bit:

public boolean isSameTree(TreeNode p, TreeNode q) {
 if (p == null || q == null) {
 return p == q;
 }
 return p.val == q.val
 && isSameTree(p.left, q.left)
 && isSameTree(p.right, q.right);
}

I flipped the operands of the == operators since having null in the right hand side reads more naturally.

I added spaces after the if and after the commas to follow the common formatting style.

• RoToRa: p == null && q == null can even be shorted to p == q in this case.
• Rob Audenaerde: @RolandIllig shorter code is not always better. I could not immediately determine why the p==q is correct here. So I would either comment it in, or be more verbose. btw I do really like the && in the return statement.