## Symmetric Binary Tree problem

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

For example, this binary tree is symmetric:

``````    1
/ \
2   2
/ \ / \
3  4 4  3
``````

But the following is not:

``````    1
/ \
2   2
\   \
3    3
``````

## Symmetric Binary Tree solution in Java

The problem can be solved easily using recursion. Two binary trees T1 and T2 are symmetric if

• the value of T1’s root node is same as the value of T2’s root node,
• T1’s left subtree is symmetric with T2’s right subtree,
• T1’s right subtree is symmetric with T2’s left subtree.

Here is the complete solution in Java:

``````class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}

class SymmetricTree {
private static boolean isSymmetric(TreeNode a, TreeNode b) {
if(a == null && b == null) {
return true;
}
if(a == null || b == null) {
return false;
}

return a.val == b.val &&
isSymmetric(a.left, b.right) &&
isSymmetric(a.right, b.left);
}

private static boolean isSymmetric(TreeNode node) {
if(node == null) {
return true;
}
return isSymmetric(node.left, node.right);
}

public static void main(String[] args) {
TreeNode node = new TreeNode(1);
node.left = new TreeNode(2);
node.right = new TreeNode(2);
node.left.left = new TreeNode(3);
node.left.right = new TreeNode(4);
node.right.left = new TreeNode(4);
node.right.right = new TreeNode(3);

System.out.println(isSymmetric(node));
}
}
``````