Find the Level of a Binary Tree with Width K | Java program to implement the above approach ; Structure of binary tree node ; Function to create 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
import java . util . * ; class GFG { static class Node { int data ; Node left , right ; } ; static class pair { Node first ; int second ; pair ( Node first , int second ) { this . first = first ; this . second = second ; } } static Node newNode ( int data ) { Node temp = new Node ( ) ; temp . data = data ; temp . left = temp . right = null ; return temp ; } static int findLevel ( Node root , int k , int level ) { Queue < pair > qt = new LinkedList < > ( ) ; qt . add ( new pair ( root , 0 ) ) ; int count = 1 , b = 0 , a = 0 ; while ( ! qt . isEmpty ( ) ) { pair temp = qt . peek ( ) ; qt . poll ( ) ; if ( count == 1 ) { b = temp . second ; } if ( temp . first . left != null ) { qt . add ( new pair ( temp . first . left , 2 * temp . second ) ) ; } if ( temp . first . right != null ) { qt . add ( new pair ( temp . first . right , 2 * temp . second + 1 ) ) ; } count -- ; if ( count == 0 ) { if ( ( b - a + 1 ) == k ) return level ; pair secondLabel = qt . peek ( ) ; a = secondLabel . second ; level += 1 ; count = qt . size ( ) ; } } return - 1 ; } public static void main ( String [ ] args ) { 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 ; System . out . println ( findLevel ( root , k , 1 ) ) ; } }