Showing posts with label Mirroring Binary Tree. Show all posts
Showing posts with label Mirroring Binary Tree. Show all posts

## Convert a Binary Tree into its Mirror Tree

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged as given below example.

```public class MirroringBinaryTree {

class NODE {

int data;
NODE left;
NODE right;

public NODE(int data) {
this.data = data;
left = right = null;
}
}

public static void main(String[] args) {

MirroringBinaryTree obj = new MirroringBinaryTree();

int val[] = new int[] { 23, 34, 12, 10, 36, 35, 40, 55 };

NODE root = obj.createBinaryTree(val);

System.out.print("\n\n INORDER ::::::: ");
obj.inOrderTraversal(root);

root = obj.mirror(root);

System.out.print("\n\n INORDER AFTER MIRROR::::::: ");
obj.inOrderTraversal(root);
}

/*
* Mirror the binary tree
*/
public NODE mirror(NODE node) {
if (node == null)
return node;

NODE left = mirror(node.left);
NODE right = mirror(node.right);

/* swap left and right pointers */
node.left = right;
node.right = left;

return node;
}

/*
*  BST in-order traversal
*/
public void inOrderTraversal(NODE root) {

if (root.left != null) {
inOrderTraversal(root.left);
}

System.out.print(root.data + ", ");

if (root.right != null) {
inOrderTraversal(root.right);
}
}

/*
* Create binary tree by given array
*/
public NODE createBinaryTree(int val[]) {
NODE root = null;
for (int i : val) {
NODE tmp = new NODE(i);
if (root == null) {
root = tmp;
} else {
NODE lastNode = getLastNode(root, i);
if (i > lastNode.data) {
lastNode.right = tmp;
} else {
lastNode.left = tmp;
}
}
}
return root;
}

/*
* Get parent node the join current node
*/
public NODE getLastNode(NODE root, int val) {

if (val > root.data) {

if (root.right == null) {
return root;
} else
return getLastNode(root.right, val);
} else {

if (root.left == null) {
return root;
} else
return getLastNode(root.left, val);
}
}
}
```

OUTPUT:

``` INORDER ::::::: 10, 12, 23, 34, 35, 36, 40, 55,

INORDER AFTER MIRROR::::::: 55, 40, 36, 35, 34, 23, 12, 10,
```