Print the middle nodes of each level of a Binary Tree | C ++ program for the above approach ; Structure Node of Binary Tree ; Function to create a new node ; Return the created node ; Function that performs the DFS traversal on Tree to store all the nodes at each level in map M ; Base Case ; Push the current level node ; Left Recursion ; Right Recursion ; Function that print all the middle nodes for each level in Binary Tree ; Stores all node in each level ; Perform DFS traversal ; Traverse the map M ; Get the size of vector ; For odd number of elements ; Print ( M / 2 ) th Element ; Otherwise ; Print ( M / 2 ) th and ( M / 2 + 1 ) th Element ; Driver Code ; Given Tree ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int data ; struct node * left ; struct node * right ; } ; struct node * newnode ( int d ) { struct node * temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> data = d ; temp -> left = NULL ; temp -> right = NULL ; return temp ; } void dfs ( node * root , int l , map < int , vector < int > > & M ) { if ( root == NULL ) return ; M [ l ] . push_back ( root -> data ) ; dfs ( root -> left , l + 1 , M ) ; dfs ( root -> right , l + 1 , M ) ; } void printMidNodes ( node * root ) { map < int , vector < int > > M ; dfs ( root , 0 , M ) ; for ( auto & it : M ) { int size = it . second . size ( ) ; if ( size & 1 ) { cout << it . second [ ( size - 1 ) / 2 ] << endl ; } else { cout << it . second [ ( size - 1 ) / 2 ] << ' ▁ ' << it . second [ ( size - 1 ) / 2 + 1 ] << endl ; } } } int main ( ) { struct node * root = newnode ( 1 ) ; root -> left = newnode ( 2 ) ; root -> right = newnode ( 3 ) ; root -> left -> left = newnode ( 4 ) ; root -> left -> right = newnode ( 5 ) ; root -> left -> right -> left = newnode ( 11 ) ; root -> left -> right -> right = newnode ( 6 ) ; root -> left -> right -> right -> left = newnode ( 7 ) ; root -> left -> right -> right -> right = newnode ( 9 ) ; root -> right -> left = newnode ( 10 ) ; root -> right -> right = newnode ( 8 ) ; printMidNodes ( root ) ; return 0 ; }