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
 

River Crossing Problem

Question 1

Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?

Answer

The initial solution most people will think of is to use the fastest person as an usher to guide everyone across. How long would that take? 10 + 1 + 7 + 1 + 2 = 21 mins. Is that it? No. That would make this question too simple even as a warm up question.

To reduce the amount of time, we should find a way for 10 and 7 to go together.

So the solution is

1 and 2 go cross
2 comes back
7 and 10 go across
1 comes back
1 and 2 go across (done)
Total time = 2 + 2 + 10 + 1 + 2 = 17 mins

Question 2

A guard is positioned at the one side of bridge say 'A'.
* His task is to shoot all those who try to leave from 'A' to other side say 'B'.
* He also need to welcome the person who come from other side 'B' to his side 'A'.

The guard comes out of his post every 1 hour and looks down the bridge for any people trying to leave.
Monica a brilliant girl is at side 'A' and wish to go to other side 'B'. She also know's it would take her 1:45 hr to cross the river.

She comes with an super idea and able to cross the river.How did Monica cross the river ? 

Answer

Steps
1. Monica go from side A to B for approx 59 minutes
2. Lisa then move back to side A for 2 minutes to fool guard. Now guard will think she is coming to side A.
3. then she again move toward B

Piece of Cake

Question

How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut.

Possible Solution

1.  The simplest solution that one might think of is to cut the cake horizontally along the height of the cake. That would divide the cake in exact two equal pieces.This solution won't work if there is some frosting on the top which also needs to be divided.
2. Other possible solution would be to make a cut such that it passes through center of both the rectangles. Since the cut halves both the rectangles, the resulting two pieces are guaranteed to have equal area.