text: Connect nodes at same level | C program to connect nodes at same level using extended pre - order traversal ; A binary tree node ; Sets the nextRight of root and calls connectRecur ( ) for other nodes ; Set the nextRight for root ; Set the next right for rest of the nodes ( other than root ) ; Set next right of all descendents of p . Assumption : p is a compete binary tree ; Base case ; Set the nextRight pointer for p 's left child ; Set the nextRight pointer for p 's right child  p->nextRight will be NULL if p is the right  most child at its level ; Set nextRight for other nodes in pre order fashion ; 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 ; Populates nextRight pointer in all nodes ; Let us check the values of nextRight pointers
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE void connectRecur ( struct node * p ) ; struct node { int data ; struct node * left ; struct node * right ; struct node * nextRight ; } ; void connect ( struct node * p ) { p -> nextRight = NULL ; connectRecur ( p ) ; } void connectRecur ( struct node * p ) { if ( ! p ) return ; if ( p -> left ) p -> left -> nextRight = p -> right ; if ( p -> right ) p -> right -> nextRight = ( p -> nextRight ) ? p -> nextRight -> left : NULL ; connectRecur ( p -> left ) ; connectRecur ( p -> right ) ; } struct node * newnode ( int data ) { struct node * node = ( struct node * ) malloc ( sizeof ( struct node ) ) ; node -> data = data ; node -> left = NULL ; node -> right = NULL ; 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 ) ; connect ( root ) ; printf ( " Following ▁ are ▁ populated ▁ nextRight ▁ pointers ▁ in ▁ 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 ) ; return 0 ; }