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

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

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.

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

1. Node A does not have any sibling.
   • Node A nextSibling will be set to null.
2. 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]
3. 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
4. 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

Download Code-Next sibling reference in Binary Tree DFS