Connect nodes at same level (set next sibling)

Given a binary tree, we want to connect the nodes or siblings at same level using recursive algorithm.
Perform preOrder traversal of a binary tree using depth first search recursive algorithm.
The node at every level will hold a reference of its immediate next (or right) sibling (if exists).
In a binary tree, we generally have following information.
- Data node
- Left Child
- Right Child

To have next sibling reference, we will add another field to a binary tree i.e. nextSibling, which will connects the sibling nodes at same level. With addition of next reference, binary tree will looks like as shown in the Fig 1.

Set next sibling pointer tree — Fig 1: Next Sibling reference in binary tree

Example – connect nodes at same level

Nodes at same level are connected (Refer Fig 2).
Level 0:
- Node A (root node) does not have right sibling node.
- A.next set to null.
At level 1
- Node B.next set to next sibling Node C
  - B.next = C.
- Node C does not have any right sibling.
  - C.next = null.
Similarly, Nodes at Level 2 are connected.

connect node level tree — Fig 2: Next sibling in a binary tree

Algorithm – set next reference (or next Sibling) of nodes at same level

Node A does not have any sibling.
- Node A nextSibling will be set to null.
Setting nextSibling reference for Node A’ left (B) & right child (C)
- A’s left child i.e. B next reference set to A’s right child
  - Node B will start pointing to Node C
    - A.left.nextSibling = A.right [Node B]
- A’s right child i.e. Node C
  - Node A does not have any siblings
    - So Node A’s right child C will not have any sibling
  - Simply set the Node C right child to null
    - A.right.nextSibling = null [Node C]
Setting the next reference for Node B’s left (Node D) and right child (Node E)
- B’ left child i.e. D next reference set to B’s right child
  - Node D will start pointing to Node E
    - B.left.nextSibling = B.right [Node D]
- B’s right child i.e. Node E
  - As Node B have sibling [Set in step 2]
  - Setting the Node E next child as follow
    - Set the next of B.right [Node E] to left of B.next [Node C]
    - Node E will start pointing to Node F
      - B.right.nextSibling = B.nextSibling.left
Similarly set the next reference for rest of nodes in a binary tree.

Algorithm conclusion

Left child of current node set to right child of current node [Condition 1]
Right child of current node will have two condition [Condition 2 and Condition 3]
- Current node having next sibling [Example: Node B & Node C are siblings]
- Current Node does not have any next sibling [Example: Node A does not having any sibling]

Program – Connect the siblings of binary tree using DFS algorithm.

1.) NextSiblingPointer Class:

Perform pre order traversal of binary tree.
Setting the nextSibling reference of nodes as per above algorithm.

package org.learn.Question;
 
import org.learn.PrepareTree.Node;
 
public class NextSiblingPointer {
    public static void nextSiblingPointer(Node node) {
        if(null == node) {
            return;
        }
        //if we have left child
        if(node.left != null) {
            node.left.nextSibling = node.right;
        }
         
        //if we have right child
        if(node.right != null) {
            //if current node has sibling, then left set
            //
            if(node.nextSibling != null) {
                node.right.nextSibling = 
                                           node.nextSibling.left;
            } else {
                node.right.nextSibling = null;
            }
        }
        nextSiblingPointer(node.left);
        nextSiblingPointer(node.right);
        return;
    }   
    public static void printUsingNextSibling(Node root) {
        Node node = null;
        int level = 0;
        while( root != null) {
            node = root;
            System.out.printf("Level %d data ",level++);
            while(node != null) {           
                System.out.printf("%d ",node.data);
                node = node.nextSibling;
            }
            System.out.println("");
            root = root.left;
        }
    }
}

2.) Node Class:

The class representing the nodes of binary tree. Node class has following attributes

Data Node
left child
right child
nextSibling

package org.learn.PrepareTree;
 
public class Node {
    public int data;
    public Node left;
    public Node right;
    public Node nextSibling;
 
    public Node(int num) {
        this.data = num;
        this.left = null;
        this.right = null;
        this.nextSibling = null;
    }
 
    public Node() {
        this.left = null;
        this.right = null;
        this.nextSibling = null;
    }
    public static Node createNode(int number) {
        return new Node(number);
    }
}

3.) App Class:

We are creating the binary tree in main function & calling NextSiblingPointer class to connect the sibling nodes in a binary tree.

package org.learn.Client;
 
import org.learn.PrepareTree.Node;
import org.learn.Question.NextSiblingPointer;
 
public class App 
{
    public static void main( String[] args )
    {       
       /*
                     1
                   /   \    
                  2     3
                 / \   / \ 
                4   5 6   7       
         
        */
    Node root = Node.createNode(1);
    root.left = Node.createNode(2);
    root.right = Node.createNode(3);
     
        // left sub tree
    root.left.left = Node.createNode(4);
    root.left.right = Node.createNode(5);
 
    // right subtree
    root.right.left = Node.createNode(6);
    root.right.right = Node.createNode(7);
 
        NextSiblingPointer.nextSiblingPointer(root);        
        NextSiblingPointer.printUsingNextSibling(root);    
    }
}

Output – connect nodes at same level (set next sibling) in binary tree

Level 0 data 1
Level 1 data 2 3
Level 2 data 4 5 6 7

Connect nodes at same level (set next sibling)-binary tree DFS/example

Example – connect nodes at same level

Algorithm – set next reference (or next Sibling) of nodes at same level

Algorithm conclusion

Program – Connect the siblings of binary tree using DFS algorithm.

1.) NextSiblingPointer Class:

2.) Node Class:

3.) App Class:

Output – connect nodes at same level (set next sibling) in binary tree

Download Code-Next sibling reference in Binary Tree DFS

Example – connect nodes at same level

Algorithm – set next reference (or next Sibling) of nodes at same level

Algorithm conclusion

Program – Connect the siblings of binary tree using DFS algorithm.

1.) NextSiblingPointer Class:

2.) Node Class:

3.) App Class:

Output – connect nodes at same level (set next sibling) in binary tree

You may also like: