Home » Algorithm » Binary Search Tree » Binary Tree » Datastructure » Java » Connect nodes at same level in a Binary Tree.

Connect nodes at same level in a Binary Tree.

in , , , , - on 14:15:00 - No comments

How to connect nodes at same level using Queue? OR
Populate next right pointers for each Tree Node? OR
Connect nodes of a binary tree at same Level?

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
 Binary Tree is given to you,
  1. some node of  tree has both left and right child present,
  2. some node of tree has only left child present and
  3. some node of tree has only right child present, 
  4. nextRight pointer of all the node initially is null. 
Our task is to connect nextRight pointer of each node to its adjacent node.  
  1. If the immediate adjacent node is not present then connect to next adjacent node and 
  2. If next adjacent node is not present then connect to next to next adjacent node and 
  3. If next to next adjacent node is not present then search until you find the adjacent node along the same Level and connect to it.
  4. If the adjacent node is not present at same level then connect it to null. 

Structure of the given Binary Tree Node is like following:
package javabypatel.tree;

class Node{
 private int data;
 private Node left;
 private Node right;
 private Node nextRight;  <---- New pointer introduced to connect to adjacent Node.
}

See below image for better understanding the problem statement.


What is adjacent node?

Look at the below elaborated Case 2 image, 
Immediate adjacent node of Node 7 is not present as Node 3 doesn't has right child. 
Next to adjacent node is also not present as Node 8 doesn't has left child, 
Also next to next adjacent node is not present as Node 8 doesn't has right child. 

While searching along the same Level, we see Node 25 is present and it has right child present, 
So connect Node 7 nextRight pointer to Node 30.
  

Algorithm

If we know how to traverse the Tree level by level from Left to Right, then we can very well connect nodes to its adjacent node by extending the logic..

How to read the tree level by level: Refer: Level Order Traversal.

Levelorder traversal of the above sample tree will outputs:      
10  5  20  3  8  25  7  30

Solution:
1. What first thing we have to do is to take a Queue for reading the tree in Level order fashion. 
 
2. Read all nodes at the same level and enQueue it in queue, 

3. Once all the nodes of a same level are read and enqueued in queue. 
    add some notation in a queue which represent the end of level, otherwise we will not come to 
    know where one level has started and ended in queue. so we will add dummy entry NULL 

4. Now, once the queue is filled with Level 1, Queue will look like below image,

we will not able to read other levels until and unless we will read Level 1 data already present in the Queue (because data present in Level 2 that is Node 5 and Node 20 is actually Left and Right child of Node 10, which is present in Queue).

If you observe in the Binary Tree, Node 10 nextRight pointer is connecting to null.

From the Queue, we can see the relation that if we connect nextRight pointer of Node present at head (Node 10) of a queue to the Node present just after it (null),  then Node 10 nextRight pointer will get connected to null and our task for first level is completed.
  
For inserting level 2 data in queue, what we will do is, once we read the Node from the Queue (in our case Node 10 is first node we read) put the Left and Right child (if present) of that node in the queue.
   
After deQueue Node 10 from queue and putting its child node 5 and 20 in queue, 
Queue will look like below image,
 
the next node in the queue we will encounter is null. 
which signifies the end of 1st level and 
It also signifies that all left and right child of 1st level nodes and done putting in the queue, 
and Queue is now filled with Level 2 nodes, So we have to putt null node at the end of the queue
for identification that Level 2 nodes is getting completed at that point and whatever added after
that null will be part of Level 3 nodes. 
   
   Queue will look like below image after reading null in above queue,

   Repeat step 3 and remember the basic rule,
Node node  = queue.dequeue(); 
 node.setNextRight(elementAtHeadOfQueue);
    If node is null it signifies end of level and 
    If node is not null then simply do node.setNextRight(elementAtHeadOfQueue);  and put left 
    and right child of node in queue.
 Overview:


Java Program for Connecting nodes at Same Level in Binary Tree.
(Extend Level Order Traversal or BFS approach)

ConnectNodesAtSameLevel.java 
package javabypatel.tree;

import java.util.LinkedList;
import java.util.Queue;

public class ConnectNodesAtSameLevel {

 public static void main(String[] args) {
  Node rootNode=null;

  rootNode  = addNode(rootNode, 10, true);
  rootNode  = addNode(rootNode, 5, true);
  rootNode  = addNode(rootNode, 2, true);

  rootNode  = addNode(rootNode, 30, true);
  rootNode  = addNode(rootNode, 40, true);
  
  linkNodesAtSameLevelWithExtraSpace(rootNode);
  System.out.println(rootNode);  
 }

 private static void linkNodesAtSameLevelWithExtraSpace(Node rootNode){
  if (rootNode == null) return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(rootNode); // Adding Level 1 in Queue
  queue.add(null);

  while (!queue.isEmpty()){ 
   Node node = queue.poll();

   if(node!=null){
    node.setNextRight(queue.peek()); // setting nextRight to head of Queue.

    if(node.getLeft()!=null) // adding entries in Queue for Next Level
     queue.add(node.getLeft());

    if(node.getRight()!=null) // adding entries in Queue for Next Level
     queue.add(node.getRight());

   }else{

   // checking if queue head is null, if it is null then this is end of all levels 
   // and if queue head is not null then this is end of level and adding null to indicate end of level.
    if(queue.peek()!=null) 
     queue.add(null);

   }
  }
 }

 private static Node addNode(Node rootNode, int i, boolean isRootNode) {
  if(rootNode==null){
   return new Node(i);
  }else{
   if(i > rootNode.getData()){
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }

   }else{
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }
   }
  }
  return rootNode;
 }
}

package javabypatel.tree;

class Node{
 private int data;
 private Node left;
 private Node right;
 private Node nextRight;

 public Node(int data) {
  this.data=data;
 }

 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public Node getLeft() {
  return left;
 }
 public void setLeft(Node left) {
  this.left = left;
 }
 public Node getRight() {
  return right;
 }
 public void setRight(Node right) {
  this.right = right;
 }
 public Node getNextRight() {
  return nextRight;
 }
 public void setNextRight(Node nextRight) {
  this.nextRight = nextRight;
 }
}

You may also like to see

How to connect nodes at same level using constant extra space

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.



Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.
Categories: , , , ,

Post a Comment