Trees

Symmetric Binary Tree (Mirror image of itself) problem

Rajeev SinghAlgorithms1 mins read

Symmetric Binary Tree

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