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
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