Friday 30 August 2013

Check whether a given tree is symmetric with structure wise or not

How will you check whether a given tree is symmetric with structure wise or not.

Ex:
Symmetric (structure wise)
            5
          /   \
         3    9
         \   /
         4  8

 Not symmetric

            5
          /   \
         5     9
        /      /
       3     8

Implementation

class CheckForSymmetricTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;

public Tree(int data){
this.data = data;
}

//create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}
}

public static boolean isSymmetric(Tree root){
if(root == null)
return true;

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

public static boolean isSymmetric(Tree r1, Tree r2){
if(r1==null && r2==null)
return true;

if(r1==null || r2==null)
return false;

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

public static void main(String []args){
int []a = {1,2,3,4,5,6,7};

Tree root = Tree.createBST(a, 0, a.length - 1);

boolean result = isSymmetric(root);

if(result)
System.out.println("Given tree is a symmetric tree");
else
System.out.println("Given tree isn't a symmetric tree");
}

}

Output : Given tree is a symmetric tree

No comments:

Post a Comment