Site icon

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

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.

Fig 1: Next Sibling reference in binary tree

Example – connect nodes at same level

Fig 2: Next sibling in a binary tree

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

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

1.) NextSiblingPointer Class:

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

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:

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

Exit mobile version