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