Count nodes from all lower levels smaller than minimum valued node of current level for every level in a Binary Tree | C ++ program of the above approach ; Stores the nodes to be deleted ; Structure of a Tree node ; Function to create a new node ; Function to find the min value of node for each level ; Count is used to diffentiate each level of the tree ; Function to check whether the nodes in the level below it are smaller by performing post order traversal ; Traverse the left subtree ; Traverse right subtree ; Check from minimum values computed at each level ; Function to print count of nodes from all lower levels having values less than the the nodes in the current level ; Stores the number of levels ; Stores the required count of nodes for each level ; Driver Code ; 4 / \ 3 5 / \ / \ 10 2 3 1
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_map < int , bool > mp ; 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 ) ; } void calculateMin ( Node * root , vector < int > & levelMin ) { queue < Node * > qt ; qt . push ( root ) ; int count = 1 ; int min_v = INT_MAX ; while ( ! qt . empty ( ) ) { Node * temp = qt . front ( ) ; min_v = min ( min_v , temp -> key ) ; qt . pop ( ) ; if ( temp -> left ) { qt . push ( temp -> left ) ; } if ( temp -> right ) { qt . push ( temp -> right ) ; } count -- ; if ( count == 0 ) { levelMin . push_back ( min_v ) ; min_v = INT_MAX ; count = qt . size ( ) ; } } } void findNodes ( Node * root , vector < int > & levelMin , vector < int > & levelResult , int level ) { if ( root == NULL ) return ; findNodes ( root -> left , levelMin , levelResult , level + 1 ) ; findNodes ( root -> right , levelMin , levelResult , level + 1 ) ; for ( int i = 0 ; i < level ; i ++ ) { if ( root -> key <= levelMin [ i ] ) { levelResult [ i ] += 1 ; } } } void printNodes ( Node * root ) { vector < int > levelMin ; calculateMin ( root , levelMin ) ; int numLevels = levelMin . size ( ) ; vector < int > levelResult ( numLevels , 0 ) ; findNodes ( root , levelMin , levelResult , 0 ) ; for ( int i = 0 ; i < numLevels ; i ++ ) { cout << levelResult [ i ] << " ▁ " ; } } int main ( ) { Node * root = newNode ( 4 ) ; root -> left = newNode ( 3 ) ; root -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 3 ) ; root -> right -> right = newNode ( 1 ) ; root -> left -> left = newNode ( 10 ) ; root -> left -> right = newNode ( 2 ) ; printNodes ( root ) ; }