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.

Related Links

• DataStructures github link

Deepest left leaf node in a binary tree

Question : 

Given a Binary Tree, find the deepest leaf node that is left child of its parent. For example, consider the following tree. The deepest left leaf node is the node with value 9.

Code:

 public class DeepestLeftLeafNodeFinder {

    Node deepestNode;
    int deepestNodeDepth;

    public Node findDeepestLeftLeafNode(Node root,boolean isLeftNode,int depth){

        if(isLeftNode){
            if(depth > deepestNodeDepth){
                deepestNode = root;
                deepestNodeDepth = depth;
            }
        }

        if(root.getLeft() != null){
            findDeepestLeftLeafNode(root.getLeft(),true,depth + 1);
        }

        if(root.getRight() != null){
            findDeepestLeftLeafNode(root.getRight(),false,depth+1);
        }

        return deepestNode;
    }
}

Test :

    public static void main(String args[]){

        Node root = new Node(1);

        Node l = new Node(2);
        root.setLeft(l);
        Node r = new Node(3);
        root.setRight(r);

        Node l1 = new Node(4);
        l.setLeft(l1);

        Node r1 = new Node(5);
        r.setLeft(r1);
        Node r2 = new Node(6);
        r.setRight(r2);

        Node r12 = new Node(7);
        r1.setRight(r12);

        Node r121 = new Node(9);
        r12.setLeft(r121);

        Node r22 = new Node(8);
        r2.setRight(r22);

        Node r222 = new Node(10);
        r22.setRight(r222);

        System.out.println("Deepest left node of the tree is : " +
                new DeepestLeftLeafNodeFinder().findDeepestLeftLeafNode(root,false,0).getValue());
    }

Output :

Deepest left node of the tree is : 9 

Note : Complexity of above code is O(N) as we are visiting each node at most once. Do let me know if anyone has a better solution.

Find next right node of a given key

Question : Find next right node of a given key

Given a Binary tree and a key in the binary tree, find the node right to the given key. If there is no node on right side, then return NULL. Expected time complexity is O(n) where n is the number of nodes in the given binary tree.
For example, consider the following Binary Tree. Output for 2 is 6, output for 4 is 5. Output for 10, 6 and 5 is NULL.

Code : 

package in.blogspot.osg.Demo;
import java.util.LinkedList;
import java.util.Queue;

public class RightNodeFinder {
    
    Queue<Node> nodeQueue = new LinkedList<Node>();
    Queue<Integer> levelQueue = new LinkedList<Integer>();
       
    public Node findRightNode(int value, Node root, int level){

        if(value == root.getValue()){
            if(nodeQueue.isEmpty()){
                return null;
            }
            else{
                if(levelQueue.peek() != level){
                    return null;
                }
                else{
                    return nodeQueue.poll();
                }
            }
        }
        else{           
            if(root.getLeft() != null){
                nodeQueue.offer(root.getLeft());
                levelQueue.offer(level + 1);
            }
            if(root.getRight() != null){
                nodeQueue.offer(root.getRight());
                levelQueue.offer(level + 1);
            }
            if(!nodeQueue.isEmpty()){
                return findRightNode(value, nodeQueue.poll(), levelQueue.poll());
            }   
        }
        return null;
    }
}

Now lets test the code. You can see the code for Node data structure in this post. 

    public static void main(String args[]){
        
        Node root = new Node(10);
        Node l = new Node(2);
        Node r = new Node(6);
        Node l1 = new Node(8);
        Node l2 = new Node(4);
        Node r2 = new Node(5);
        
        root.setLeft(l);
        root.setRight(r);
        l.setLeft(l1);
        l.setRight(l2);
        r.setRight(r2);
        
        System.out.println("Right Node of node with value 10 is : " + new RightNodeFinder().findRightNode(10, root, 0));
        System.out.println("Right Node of node with value 2 is : " + new RightNodeFinder().findRightNode(2, root, 0));
        System.out.println("Right Node of node with value 6 is : " + new RightNodeFinder().findRightNode(6, root, 0));
        System.out.println("Right Node of node with value 8 is : " + new RightNodeFinder().findRightNode(8, root, 0));
        System.out.println("Right Node of node with value 4 is : " + new RightNodeFinder().findRightNode(4, root, 0));
        System.out.println("Right Node of node with value 5 is : " + new RightNodeFinder().findRightNode(5, root, 0));
    }

Output : 

 

Right Node of node with value 10 is : null
Right Node of node with value 2 is : Data is : null and Value is : 6
Right Node of node with value 6 is : null
Right Node of node with value 8 is : Data is : null and Value is : 4
Right Node of node with value 4 is : Data is : null and Value is : 5
Right Node of node with value 5 is : null

Finding Height of a binary tree

Question :  

To find height of any binary tree

Code :

public class TreeHeightFinder {

    public static int findHeight(Node root){

        int leftHeight = 0;
        int rightHeight = 0;

        if(root.getLeft() != null){
            leftHeight = findHeight(root.getLeft());
        }
        if(root.getRight() != null){
            rightHeight = findHeight(root.getRight());
        }

        int maxHeight =  max(leftHeight,rightHeight);

        return 1 + maxHeight;

    }

    public static int max(int a,int b){

        return a > b ? a : b;

    }
} 

Now lets build a tree and test it(tree is like below)

    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("Height is : " + TreeHeightFinder.findHeight(root));
    }

Output :

Height is : 3

Replace the data of each node by the sum of data of all its descendent nodes

Question :

Given a Binary Tree, replace the data of each node by the sum of data of all its descendent nodes.(Leaf nodes will have 0)

 Solution : 

The solution is simple recursive one.  For each node you need to set value of the node equal to the sum of value of it's left and right node. Each sub node will in turn calculate their value and based on sum of their children and return the sum with it's original value added.

Before providing the solution lets view the problem graphically

Before we process the tree lets say it is something like below

 The final result we are interested is 

Lets write the code for it. Note the code for Node data structure as well as various traversals is provided in this post which was poster earlier. There is a slight modification that we are adding and int value instance variable along with its getters ans setters. There is corresponding change in the constructor but the logic remains same.

Code : 

package in.blogspot.osg.Demo;

public class ReplaceWithDescendantSum {
    
    public static int replace(Node root){
        
        int rightValue = 0;
        int leftValue = 0 ;
        
        if(root.getRight() != null)
            rightValue = replace(root.getRight());
        if(root.getLeft() != null)
            leftValue = replace(root.getLeft());
        
        int sumOfDesendants = rightValue + leftValue;
        int retunValue = root.getValue() + sumOfDesendants;
        root.setValue(sumOfDesendants);
        return (retunValue);
        
    }

}

Above code will do the job.

 Lets write the main() method to test this out.

    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("***Before***");
        PreOrder.printPreOrder(root);
        ReplaceWithDescendantSum.replace(root);
        System.out.println("**After**");
        PreOrder.printPreOrder(root);
        
    }

Output : 

 

***Before***
Value : 1
Value : 2
Value : 12
Value : 13
Value : 3
Value : 6
Value : 8
**After**
Value : 44
Value : 25
Value : 0
Value : 0
Value : 14
Value : 0
Value : 0