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 :

```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

1 comment:

1. could you please add some explanation to your code as comments? thanks

t> UA-39527780-1