Connect Nodes at same Level ( Level Order Traversal ) | Connect nodes at same level using level order traversal . ; Node class ; Sets nextRight of all nodes of a tree ; null marker to represent end of current level ; Do Level order of tree using NULL markers ; next element in queue represents next node at current Level ; push left and right children of current node ; if queue is not empty , push NULL to mark nodes at this level are visited ; Driver program to test above functions ; Constructed binary tree is 10 / \ 8 2 / \ 3 90 ; Populates nextRight pointer in all nodes ; Let us check the values of nextRight pointers
import java . util . LinkedList ; import java . util . Queue ; public class Connect_node_same_level { static class Node { int data ; Node left , right , nextRight ; Node ( int data ) { this . data = data ; left = null ; right = null ; nextRight = null ; } } ; static void connect ( Node root ) { Queue < Node > q = new LinkedList < Node > ( ) ; q . add ( root ) ; q . add ( null ) ; while ( ! q . isEmpty ( ) ) { Node p = q . peek ( ) ; q . remove ( ) ; if ( p != null ) { p . nextRight = q . peek ( ) ; if ( p . left != null ) q . add ( p . left ) ; if ( p . right != null ) q . add ( p . right ) ; } else if ( ! q . isEmpty ( ) ) q . add ( null ) ; } } public static void main ( String args [ ] ) { Node root = new Node ( 10 ) ; root . left = new Node ( 8 ) ; root . right = new Node ( 2 ) ; root . left . left = new Node ( 3 ) ; root . right . right = new Node ( 90 ) ; connect ( root ) ; System . out . println ( "Following are populated nextRight pointers in NEW_LINE" + " the ▁ tree ▁ ( -1 ▁ is ▁ printed ▁ if ▁ there ▁ is ▁ no ▁ nextRight ) " ) ; System . out . println ( " nextRight ▁ of ▁ " + root . data + " ▁ is ▁ " + ( ( root . nextRight != null ) ? root . nextRight . data : - 1 ) ) ; System . out . println ( " nextRight ▁ of ▁ " + root . left . data + " ▁ is ▁ " + ( ( root . left . nextRight != null ) ? root . left . nextRight . data : - 1 ) ) ; System . out . println ( " nextRight ▁ of ▁ " + root . right . data + " ▁ is ▁ " + ( ( root . right . nextRight != null ) ? root . right . nextRight . data : - 1 ) ) ; System . out . println ( " nextRight ▁ of ▁ " + root . left . left . data + " ▁ is ▁ " + ( ( root . left . left . nextRight != null ) ? root . left . left . nextRight . data : - 1 ) ) ; System . out . println ( " nextRight ▁ of ▁ " + root . right . right . data + " ▁ is ▁ " + ( ( root . right . right . nextRight != null ) ? root . right . right . nextRight . data : - 1 ) ) ; } }