Create loops of even and odd values in a binary tree | C ++ implementation to create odd and even loops in a binary tree ; structure of a node ; Utility function to create a new node ; preorder traversal to place the node pointer in the respective even_ptrs or odd_ptrs list ; place node ptr in even_ptrs list if node contains even number ; else place node ptr in odd_ptrs list ; function to create the even and odd loops ; forming even loop ; for the last element ; Similarly forming odd loop ; traversing the loop from any random node in the loop ; Driver program to test above ; Binary tree formation ; traversing odd loop from any random odd node ; traversing even loop from any random even node
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right , * abtr ; } ; struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = node -> abtr = NULL ; return node ; } void preorderTraversal ( Node * root , vector < Node * > * even_ptrs , vector < Node * > * odd_ptrs ) { if ( ! root ) return ; if ( root -> data % 2 == 0 ) ( * even_ptrs ) . push_back ( root ) ; else ( * odd_ptrs ) . push_back ( root ) ; preorderTraversal ( root -> left , even_ptrs , odd_ptrs ) ; preorderTraversal ( root -> right , even_ptrs , odd_ptrs ) ; } void createLoops ( Node * root ) { vector < Node * > even_ptrs , odd_ptrs ; preorderTraversal ( root , & even_ptrs , & odd_ptrs ) ; int i ; for ( i = 1 ; i < even_ptrs . size ( ) ; i ++ ) even_ptrs [ i - 1 ] -> abtr = even_ptrs [ i ] ; even_ptrs [ i - 1 ] -> abtr = even_ptrs [ 0 ] ; for ( i = 1 ; i < odd_ptrs . size ( ) ; i ++ ) odd_ptrs [ i - 1 ] -> abtr = odd_ptrs [ i ] ; odd_ptrs [ i - 1 ] -> abtr = odd_ptrs [ 0 ] ; } void traverseLoop ( Node * start ) { Node * curr = start ; do { cout << curr -> data << " ▁ " ; curr = curr -> abtr ; } while ( curr != start ) ; } int main ( ) { struct Node * root = NULL ; root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 7 ) ; createLoops ( root ) ; cout << " Odd ▁ nodes : ▁ " ; traverseLoop ( root -> right ) ; cout << endl << " Even ▁ nodes : ▁ " ; traverseLoop ( root -> left ) ; return 0 ; }