Count nodes from all lower levels smaller than minimum valued node of current level for every level in a Binary Tree | Java 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
import java . util . * ; class GFG { static Map < Integer , Boolean > mp = new HashMap < Integer , Boolean > ( ) ; static class Node { int key ; Node left , right ; } ; static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = temp . right = null ; return ( temp ) ; } static void calculateMin ( Node root , Vector < Integer > levelMin ) { Queue < Node > qt = new LinkedList < > ( ) ; qt . add ( root ) ; int count = 1 ; int min_v = Integer . MAX_VALUE ; while ( ! qt . isEmpty ( ) ) { Node temp = qt . peek ( ) ; min_v = Math . min ( min_v , temp . key ) ; qt . remove ( ) ; if ( temp . left != null ) { qt . add ( temp . left ) ; } if ( temp . right != null ) { qt . add ( temp . right ) ; } count -- ; if ( count == 0 ) { levelMin . add ( min_v ) ; min_v = Integer . MAX_VALUE ; count = qt . size ( ) ; } } } static void findNodes ( Node root , Vector < Integer > levelMin , 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 . get ( i ) ) { levelResult [ i ] += 1 ; } } } static void printNodes ( Node root ) { Vector < Integer > levelMin = new Vector < Integer > ( ) ; calculateMin ( root , levelMin ) ; int numLevels = levelMin . size ( ) ; int [ ] levelResult = new int [ numLevels ] ; findNodes ( root , levelMin , levelResult , 0 ) ; for ( int i = 0 ; i < numLevels ; i ++ ) { System . out . print ( levelResult [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { 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 ) ; } }