Count of nodes which are at a distance X from root and leaves | Python3 implementation of the approach ; 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 prnodes 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 prleaf 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
from math import log2 , ceil , floor NEW_LINE def countNodes ( N , X ) : NEW_LINE INDENT height = floor ( log2 ( N ) ) NEW_LINE if ( X > height ) : NEW_LINE INDENT print ( " 0 0 " ) NEW_LINE return NEW_LINE DEDENT if ( N == 1 ) : NEW_LINE INDENT print ( " 1 1 " ) NEW_LINE return NEW_LINE DEDENT max_total_nodes = ( 1 << ( height + 1 ) ) - 1 NEW_LINE nodes_last_level = ( 1 << height ) - ( max_total_nodes - N ) NEW_LINE from_root = 0 NEW_LINE from_leaf = 0 NEW_LINE if ( X == height ) : NEW_LINE INDENT from_root = nodes_last_level NEW_LINE DEDENT else : NEW_LINE INDENT from_root = 1 << X NEW_LINE DEDENT left_leaf_nodes = ( ( 1 << height ) - nodes_last_level ) // 2 NEW_LINE if ( X == 0 ) : NEW_LINE INDENT from_leaf = nodes_last_level + left_leaf_nodes NEW_LINE DEDENT else : NEW_LINE INDENT i = X NEW_LINE while ( nodes_last_level > 1 and i > 0 ) : NEW_LINE INDENT nodes_last_level = ceil ( nodes_last_level / 2 ) NEW_LINE i -= 1 NEW_LINE DEDENT from_leaf = nodes_last_level NEW_LINE i = X NEW_LINE while ( left_leaf_nodes > 1 and i > 0 ) : NEW_LINE INDENT left_leaf_nodes = ceil ( left_leaf_nodes / 2 ) NEW_LINE i -= 1 NEW_LINE DEDENT from_leaf += left_leaf_nodes NEW_LINE DEDENT print ( from_root ) NEW_LINE print ( from_leaf ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N , X = 38 , 3 NEW_LINE countNodes ( N , X ) NEW_LINE DEDENT