Count of nodes which are at a distance X from root and leaves | Function to find the count of the required nodes ; Height of the complete binary tree with n nodes ; If X > height then no node can be present at that level ; Corner case ; Maximum total nodes that are possible in complete binary tree with height h ; Nodes at the last level ; To store the count of nodes x dist away from root ; To store the count of nodes x dist away from leaf ; If X = h then print nodes at last level else nodes at Xth level ; 2 ^ X ; Number of left leaf nodes at ( h - 1 ) th level observe that if nodes are not present at last level then there are a / 2 leaf nodes at ( h - 1 ) th level ; If X = h then print leaf nodes at the last h level + leaf nodes at ( h - 1 ) th level ; First calculate nodes for leaves present at height h ; Then calculate nodes for leaves present at height h - 1 ; Add both the resuls ; Driver Code
function countNodes ( N , X ) { let height = Math . floor ( Math . log ( N ) / Math . log ( 2 ) ) ; if ( X > height ) { document . write ( " " ) ; return ; } if ( N == 1 ) { document . write ( " " ) ; return ; } let max_total_nodes = ( 1 << ( height + 1 ) ) - 1 ; let nodes_last_level = ( 1 << height ) - ( max_total_nodes - N ) ; let from_root ; let from_leaf ; if ( X == height ) from_root = nodes_last_level ; else from_root = 1 << X ; let left_leaf_nodes = Math . floor ( ( ( 1 << height ) - nodes_last_level ) / 2 ) ; if ( X == 0 ) { from_leaf = nodes_last_level + left_leaf_nodes ; } else { let i = X ; while ( nodes_last_level > 1 && i > 0 ) { nodes_last_level = Math . floor ( Math . ceil ( nodes_last_level / 2 ) ) ; i -- ; } from_leaf = nodes_last_level ; i = X ; while ( left_leaf_nodes > 1 && i > 0 ) { left_leaf_nodes = Math . floor ( Math . ceil ( left_leaf_nodes / 2 ) ) ; i -- ; } from_leaf += left_leaf_nodes ; } document . write ( from_root + " " + from_leaf ) ; } let N = 38 , X = 3 ; countNodes ( N , X ) ;