Root to leaf paths having equal lengths in a Binary Tree | utility that allocates a newNode with the given key ; Function to store counts of different root to leaf path lengths in hash map m . ; Base condition ; If leaf node reached , increment count of path length of this root to leaf path . ; Recursively call for left and right subtrees with path lengths more than 1. ; A wrapper over pathCountUtil ( ) ; create an empty hash table ; Recursively check in left and right subtrees . ; Print all path lenghts and their counts . ; Driver Code
class newnode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def pathCountUtil ( node , m , path_len ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( node . left == None and node . right == None ) : NEW_LINE INDENT if path_len [ 0 ] not in m : NEW_LINE INDENT m [ path_len [ 0 ] ] = 0 NEW_LINE DEDENT m [ path_len [ 0 ] ] += 1 NEW_LINE return NEW_LINE DEDENT pathCountUtil ( node . left , m , [ path_len [ 0 ] + 1 ] ) NEW_LINE pathCountUtil ( node . right , m , [ path_len [ 0 ] + 1 ] ) NEW_LINE DEDENT def pathCounts ( root ) : NEW_LINE INDENT m = { } NEW_LINE path_len = [ 1 ] NEW_LINE pathCountUtil ( root , m , path_len ) NEW_LINE for itr in sorted ( m , reverse = True ) : NEW_LINE INDENT print ( m [ itr ] , " ▁ paths ▁ have ▁ length ▁ " , itr ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newnode ( 8 ) NEW_LINE root . left = newnode ( 5 ) NEW_LINE root . right = newnode ( 4 ) NEW_LINE root . left . left = newnode ( 9 ) NEW_LINE root . left . right = newnode ( 7 ) NEW_LINE root . right . right = newnode ( 11 ) NEW_LINE root . right . right . left = newnode ( 3 ) NEW_LINE pathCounts ( root ) NEW_LINE DEDENT