Diameter of a Binary Indexed Tree with N nodes | Function to find diameter of BIT with N + 1 nodes ; L is size of subtree just before subtree in which N lies ; H is the height of subtree just before subtree in which N lies ; Base Cases ; Size of subtree are power of 2 ; 3 Cases as explained in Approach ; Driver Code
def diameter ( n ) : NEW_LINE INDENT L , H , templen = 0 , 0 , 0 ; NEW_LINE L = 1 ; NEW_LINE H = 0 ; NEW_LINE if ( n == 1 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT if ( n == 2 ) : NEW_LINE INDENT return 2 ; NEW_LINE DEDENT if ( n == 3 ) : NEW_LINE INDENT return 3 ; NEW_LINE DEDENT while ( L * 2 <= n ) : NEW_LINE INDENT L *= 2 ; NEW_LINE H += 1 ; NEW_LINE DEDENT if ( n >= L * 2 - 1 ) : NEW_LINE INDENT return 2 * H + 1 ; NEW_LINE DEDENT elif ( n >= L + ( L / 2 ) - 1 ) : NEW_LINE INDENT return 2 * H ; NEW_LINE DEDENT return 2 * H - 1 ; NEW_LINE DEDENT n = 15 ; NEW_LINE print ( diameter ( n ) ) ; NEW_LINE