Connect Nodes at same Level ( Level Order Traversal ) | Connect nodes at same level using level order traversal . ; Node structure ; 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 ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right , * nextRight ; } ; void connect ( struct Node * root ) { queue < Node * > q ; q . push ( root ) ; q . push ( NULL ) ; while ( ! q . empty ( ) ) { Node * p = q . front ( ) ; q . pop ( ) ; if ( p != NULL ) { p -> nextRight = q . front ( ) ; if ( p -> left ) q . push ( p -> left ) ; if ( p -> right ) q . push ( p -> right ) ; } else if ( ! q . empty ( ) ) q . push ( NULL ) ; } } struct Node * newnode ( int data ) { struct Node * node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; node -> data = data ; node -> left = node -> right = node -> nextRight = NULL ; return ( node ) ; } int main ( ) { struct Node * root = newnode ( 10 ) ; root -> left = newnode ( 8 ) ; root -> right = newnode ( 2 ) ; root -> left -> left = newnode ( 3 ) ; root -> right -> right = newnode ( 90 ) ; connect ( root ) ; printf ( " Following ▁ are ▁ populated ▁ nextRight ▁ pointers ▁ in ▁ STRNEWLINE " " the ▁ tree ▁ ( -1 ▁ is ▁ printed ▁ if ▁ there ▁ is ▁ no ▁ nextRight ) ▁ STRNEWLINE " ) ; printf ( " nextRight ▁ of ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , root -> data , root -> nextRight ? root -> nextRight -> data : -1 ) ; printf ( " nextRight ▁ of ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , root -> left -> data , root -> left -> nextRight ? root -> left -> nextRight -> data : -1 ) ; printf ( " nextRight ▁ of ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , root -> right -> data , root -> right -> nextRight ? root -> right -> nextRight -> data : -1 ) ; printf ( " nextRight ▁ of ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , root -> left -> left -> data , root -> left -> left -> nextRight ? root -> left -> left -> nextRight -> data : -1 ) ; printf ( " nextRight ▁ of ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , root -> right -> right -> data , root -> right -> right -> nextRight ? root -> right -> right -> nextRight -> data : -1 ) ; return 0 ; }