package tree; /* Write a Function to Check a given two Binary Trees are Mirror of each other. (Mirror Tree: Mirror Tree of a binary tree is where left and right child of every node of given binary tree is interexchange.) Input: 50 50 / \ / \ / \ / \ 20 80 80 20 / \ / \ / \ / \ 10 30 70 100 100 70 30 10 output: true */ class CheckTwoTreesAreMirrorOfEachOther{ public static void main(String[] args) { Node rootNode1=null; rootNode1 = addNode(rootNode1, 50, true); rootNode1 = addNode(rootNode1, 20, true); rootNode1 = addNode(rootNode1, 80, true); rootNode1 = addNode(rootNode1, 10, true); rootNode1 = addNode(rootNode1, 30, true); rootNode1 = addNode(rootNode1, 70, true); rootNode1 = addNode(rootNode1, 100, true); Node rootNode2=null; rootNode2 = addNode(rootNode2, 50, false); rootNode2 = addNode(rootNode2, 20, false); rootNode2 = addNode(rootNode2, 80, false); rootNode2 = addNode(rootNode2, 10, false); rootNode2 = addNode(rootNode2, 30, false); rootNode2 = addNode(rootNode2, 70, false); rootNode2 = addNode(rootNode2, 100, false); System.out.println(isMirrorImage(rootNode1, rootNode2)); } private static boolean isMirrorImage(Node tree1, Node tree2){ if(tree1==tree2){ //Both NULL check return true; } if(tree1==null || tree2==null){ //Any one of them is NULL check return false; } if(tree1.getData()!=tree2.getData()){ // Data check return false; } boolean leftCheck = isMirrorImage(tree1.getLeft(), tree2.getRight()); boolean rightCheck = isMirrorImage(tree1.getRight(), tree2.getLeft()); if(leftCheck && rightCheck){ return true; }else{ return false; } } private static Node addNode(Node rootNode, int i, boolean isRootNode1) { if(rootNode==null){ return new Node(i); }else{ if(i > rootNode.getData()){ if(isRootNode1){ Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode1); rootNode.setRight(nodeToAdd); }else{ Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode1); rootNode.setLeft(nodeToAdd); } }else{ if(isRootNode1){ Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode1); rootNode.setLeft(nodeToAdd); }else{ Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode1); rootNode.setRight(nodeToAdd); } } } return rootNode; } }
Questions on Stack, Queues, Linkedlist, Binary Trees, Sorting, Searching, Graphs etc with solution using Java Language.
Monday, 29 June 2015
Check if two binary trees are mirror image of each other. OR To check if two trees are inversions of each other or not.
Labels:
Binary Search Tree,
Binary Tree
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment