29 Nov 2013

Is Binary Tree Symmetric

Problem Statement:
       Check if the Given Binary Tree is Symmetric about the plane passing through root.

Fig: Symmetric Binary Tree about the place passing through root

Solution:
Full Source Code :  LINK
Below is the recursive implementation to check if Binary Tree is Symmetric


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
       /**
  * Sub-routine to check if Binary Tree is Symmetric
  */
 public boolean isSymmetric(Node left, Node right){
  if ( (left==null && right!=null) || (left!=null && right==null) )
   return false;

  if(left==null && right==null)
   return true;

  return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
 }

Please comment and post your suggestions.
Happy Coding!! :)

2 comments:

  1. public boolean isSymmetric(Node left, Node right){
    if ( (left==null && right!=null) || (left!=null && right==null) || left.data!=right.data )
    return false;

    if(left==null && right==null && right.data==left.data)
    return true;

    return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
    }

    Shouldn't it be added another check?

    ReplyDelete
    Replies
    1. Thanks for suggesting, you may be correct , but in this problem i am just concerned about the structure of binary tree and not the content of nodes. As u can see i have shown the above tree to be symmetric.
      Thanks again fren , keep suggesting.

      Delete