Saturday, 28 December 2013

Program to create Mirror image of a binary tree.

Question :

Write a Program in Java to print the mirror image of a given binary tree. Example is provided in following diagram


Solution :

Do a normal BFS traversal. In each call copy the left child's content to create right node of the mirror tree and the right child's content to create left child.

Code : 

public class TreeMirrorImageCreator {

    public static Node createMirrorImage(Node originalNode,Node mirroredNode){

        mirroredNode.setValue(originalNode.getValue());

        if(originalNode.getRight() != null){
            mirroredNode.setLeft(createMirrorImage(originalNode.getRight(),new Node(0)));
        }

        if(originalNode.getLeft() != null){
            mirroredNode.setRight(createMirrorImage(originalNode.getLeft(), new Node(0)));
        }

        return mirroredNode;

    }
}

Now lets write the code to test out this code.

    public static void main(String args[]){

        Node root = new Node(1);

        Node l = new Node(2);
        Node r = new Node(3);

        Node l1 = new Node(12);
        Node l2 = new Node(13);

        Node r1 = new Node(6);
        Node r2 = new Node(8);

        root.setLeft(l);
        root.setRight(r);

        l.setLeft(l1);
        l.setRight(l2);

        r.setLeft(r1);
        r.setRight(r2);

        System.out.println("Orig Tree : ");
        LevelTraversal.printLeveltraversal(root);
        Node mirroredRoot = new Node(0);
        TreeMirrorImageCreator.createMirrorImage(root,mirroredRoot);
        System.out.println("Mirrored Tree : ");
        LevelTraversal.printLeveltraversal(mirroredRoot);
}


Note :  Code for the Node data structure and level order traversal can be found here.

No comments:

Post a Comment

t> UA-39527780-1 back to top