Find the color of given node in an infinite binary tree | CPP program to find color of the node ; Function to find color of the node ; Maximum is to store maximum color ; Loop to check all the parent values to get maximum color ; Find the number into map and get maximum color ; Take the maximum color and assign into maximum variable ; Find parent index ; Return maximum color ; Function to build hash map with color ; To store color of each node ; For each number add a color number ; Assigning color ; Return hash map ; Driver code ; Build mapWithColor ; Print the maximum color
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findColor ( map < int , int > mapWithColor , int query ) { int maximum = 0 ; while ( query >= 1 ) { if ( mapWithColor . find ( query ) != mapWithColor . end ( ) ) { maximum = max ( maximum , mapWithColor [ query ] ) ; } if ( query % 2 == 1 ) query = ( query - 1 ) / 2 ; else query = query / 2 ; } return maximum ; } map < int , int > buildMapWithColor ( int arr [ ] , int n ) { map < int , int > mapWithColor ; for ( int i = 0 ; i < n ; i ++ ) { mapWithColor [ arr [ i ] ] = i + 1 ; } return mapWithColor ; } int main ( ) { int arr [ ] = { 3 , 2 , 1 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 7 ; map < int , int > mapWithColor = buildMapWithColor ( arr , n ) ; cout << findColor ( mapWithColor , k ) ; return 0 ; }