Find the Level of a Binary Tree with Width K | C ++ Program to implement the above approach ; Structure of a Tree node ; Utility function to create and initialize a new node ; Function returns required level of width k , if found else - 1 ; To store the node and the label and perform traversal ; Taking the last label of each level of the tree ; Check width of current level ; If the width is equal to k then return that level ; Taking the first label of each level of the tree ; If any level does not has width equal to k , return - 1 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } int findLevel ( Node * root , int k , int level ) { queue < pair < Node * , int > > qt ; qt . push ( make_pair ( root , 0 ) ) ; int count = 1 , b , a = 0 ; while ( ! qt . empty ( ) ) { pair < Node * , int > temp = qt . front ( ) ; qt . pop ( ) ; if ( count == 1 ) { b = temp . second ; } if ( ( temp . first ) -> left ) { qt . push ( make_pair ( temp . first -> left , 2 * temp . second ) ) ; } if ( temp . first -> right ) { qt . push ( make_pair ( temp . first -> right , 2 * temp . second + 1 ) ) ; } count -- ; if ( count == 0 ) { if ( b - a + 1 == k ) return level ; pair < Node * , int > secondLabel = qt . front ( ) ; a = secondLabel . second ; level += 1 ; count = qt . size ( ) ; } } return -1 ; } int main ( ) { Node * root = newNode ( 5 ) ; root -> left = newNode ( 6 ) ; root -> right = newNode ( 2 ) ; root -> right -> right = newNode ( 8 ) ; root -> left -> left = newNode ( 7 ) ; root -> left -> left -> left = newNode ( 5 ) ; root -> left -> right = newNode ( 3 ) ; root -> left -> right -> right = newNode ( 4 ) ; int k = 4 ; cout << findLevel ( root , k , 1 ) << endl ; return 0 ; }