Count pairs of leaf nodes in a Binary Tree which are at most K distance apart | ''Structure of a Node ; ''Stores the count of required pairs ; ''Function to perform dfs to find pair of leaf nodes at most K distance apart ; '' Return empty array if node is None ; '' If node is a leaf node and return res ; '' Traverse to the left ; '' Traverse to the right ; '' Update the distance between left  and right leaf node ; '' Count all pair of leaf nodes  which are at most K distance apart ; '' Return res to parent node ; ''Driver Code ; ''  1  / \  2 3  /  4   ; '' Given distance K ; '' Function call
class newNode : NEW_LINE INDENT def __init__ ( self , item ) : NEW_LINE INDENT self . data = item NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT result = 0 NEW_LINE def dfs ( root , distance ) : NEW_LINE INDENT global result NEW_LINE if ( root == None ) : NEW_LINE INDENT res = [ 0 for i in range ( distance + 1 ) ] NEW_LINE return res NEW_LINE DEDENT if ( root . left == None and root . right == None ) : NEW_LINE INDENT res = [ 0 for i in range ( distance + 1 ) ] NEW_LINE res [ 1 ] += 1 NEW_LINE return res NEW_LINE DEDENT left = dfs ( root . left , distance ) NEW_LINE right = dfs ( root . right , distance ) NEW_LINE res = [ 0 for i in range ( distance + 1 ) ] NEW_LINE i = len ( res ) - 2 NEW_LINE while ( i >= 1 ) : NEW_LINE INDENT res [ i + 1 ] = left [ i ] + right [ i ] NEW_LINE i -= 1 NEW_LINE DEDENT for l in range ( 1 , len ( left ) ) : NEW_LINE INDENT for r in range ( len ( right ) ) : NEW_LINE INDENT if ( l + r <= distance ) : NEW_LINE INDENT result += left [ l ] * right [ r ] NEW_LINE DEDENT DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE K = 3 NEW_LINE dfs ( root , K ) NEW_LINE print ( result ) NEW_LINE DEDENT