Connect nodes at same level | CPP program to connect nodes at same level using extended pre - order traversal ; Constructor that allocates a new node with the given data and NULL left and right pointers . ; 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 ; Driver code ; Constructed binary tree is 10 / \ 8 2 / 3 ; Populates nextRight pointer in all nodes ; Let us check the values of nextRight pointers
#include <bits/stdc++.h> NEW_LINE #include <iostream> NEW_LINE using namespace std ; class node { public : int data ; node * left ; node * right ; node * nextRight ; node ( int data ) { this -> data = data ; this -> left = NULL ; this -> right = NULL ; this -> nextRight = NULL ; } } ; void connectRecur ( node * p ) ; void connect ( node * p ) { p -> nextRight = NULL ; connectRecur ( p ) ; } void connectRecur ( 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 ) ; } int main ( ) { node * root = new node ( 10 ) ; root -> left = new node ( 8 ) ; root -> right = new node ( 2 ) ; root -> left -> left = new node ( 3 ) ; connect ( root ) ; cout << " Following ▁ are ▁ populated ▁ nextRight ▁ pointers ▁ in ▁ the ▁ tree " " ▁ ( -1 ▁ is ▁ printed ▁ if ▁ there ▁ is ▁ no ▁ nextRight ) STRNEWLINE " ; cout << " nextRight ▁ of ▁ " << root -> data << " ▁ is ▁ " << ( root -> nextRight ? root -> nextRight -> data : -1 ) << endl ; cout << " nextRight ▁ of ▁ " << root -> left -> data << " ▁ is ▁ " << ( root -> left -> nextRight ? root -> left -> nextRight -> data : -1 ) << endl ; cout << " nextRight ▁ of ▁ " << root -> right -> data << " ▁ is ▁ " << ( root -> right -> nextRight ? root -> right -> nextRight -> data : -1 ) << endl ; cout << " nextRight ▁ of ▁ " << root -> left -> left -> data << " ▁ is ▁ " << ( root -> left -> left -> nextRight ? root -> left -> left -> nextRight -> data : -1 ) << endl ; return 0 ; }