Open Source For Geeks: 12/25/13

Wednesday, 25 December 2013

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 :

<span style="font-weight: normal;">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;
    }
}
</span>

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

<span style="font-weight: normal;">    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));
    }
</span>

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