Count nodes from all lower levels smaller than minimum valued node of current level for every level in a Binary Tree | 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 ; 4 / \ 3 5 / \ / \ 10 2 3 1
class Node { constructor ( key ) { this . left = null ; this . right = null ; this . key = key ; } } function newNode ( key ) { let temp = new Node ( key ) ; return ( temp ) ; } function calculateMin ( root , levelMin ) { let qt = [ ] ; qt . push ( root ) ; let count = 1 ; let min_v = Number . MAX_VALUE ; while ( qt . length > 0 ) { let temp = qt [ 0 ] ; min_v = Math . min ( min_v , temp . key ) ; qt . shift ( ) ; if ( temp . left != null ) { qt . push ( temp . left ) ; } if ( temp . right != null ) { qt . push ( temp . right ) ; } count -- ; if ( count == 0 ) { levelMin . push ( min_v ) ; min_v = Number . MAX_VALUE ; count = qt . length ; } } } function findNodes ( root , levelMin , levelResult , level ) { if ( root == null ) return ; findNodes ( root . left , levelMin , levelResult , level + 1 ) ; findNodes ( root . right , levelMin , levelResult , level + 1 ) ; for ( let i = 0 ; i < level ; i ++ ) { if ( root . key <= levelMin [ i ] ) { levelResult [ i ] += 1 ; } } } function printNodes ( root ) { let levelMin = [ ] ; calculateMin ( root , levelMin ) ; let numLevels = levelMin . length ; let levelResult = new Array ( numLevels ) ; levelResult . fill ( 0 ) ; findNodes ( root , levelMin , levelResult , 0 ) ; for ( let i = 0 ; i < levelResult . length ; i ++ ) { document . write ( levelResult [ i ] + " " ) ; } } let 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 ) ;