Path length having maximum number of bends | Utility function to create a new node ; Recursive function to calculate the path Length having maximum number of bends . The following are parameters for this function . node - . pointer to the current node Dir - . determines whether the current node is left or right child of it 's parent node bends -. number of bends so far in the current path. maxBends -. maximum number of bends in a path from root to leaf soFar -. Length of the current path so far traversed Len -. Length of the path having maximum number of bends ; Base Case ; Leaf node ; Having both left and right child ; Helper function to call findMaxBendsUtil ( ) ; Call for left subtree of the root ; Call for right subtree of the root ; Include the root node as well in the path Length ; Driver code ; Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2 \ 1 / 9
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . left = None NEW_LINE self . right = None NEW_LINE self . key = key NEW_LINE DEDENT DEDENT def findMaxBendsUtil ( node , Dir , bends , maxBends , soFar , 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 ( bends > maxBends [ 0 ] ) : NEW_LINE INDENT maxBends [ 0 ] = bends NEW_LINE Len [ 0 ] = soFar NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( Dir == ' l ' ) : NEW_LINE INDENT findMaxBendsUtil ( node . left , Dir , bends , maxBends , soFar + 1 , Len ) NEW_LINE findMaxBendsUtil ( node . right , ' r ' , bends + 1 , maxBends , soFar + 1 , Len ) NEW_LINE DEDENT else : NEW_LINE INDENT findMaxBendsUtil ( node . right , Dir , bends , maxBends , soFar + 1 , Len ) NEW_LINE findMaxBendsUtil ( node . left , ' l ' , bends + 1 , maxBends , soFar + 1 , Len ) NEW_LINE DEDENT DEDENT DEDENT def findMaxBends ( node ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT Len = [ 0 ] NEW_LINE bends = 0 NEW_LINE maxBends = [ - 1 ] NEW_LINE if ( node . left ) : NEW_LINE INDENT findMaxBendsUtil ( node . left , ' l ' , bends , maxBends , 1 , Len ) NEW_LINE DEDENT if ( node . right ) : NEW_LINE INDENT findMaxBendsUtil ( node . right , ' r ' , bends , maxBends , 1 , Len ) NEW_LINE DEDENT Len [ 0 ] += 1 NEW_LINE return Len [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 10 ) NEW_LINE root . left = newNode ( 8 ) NEW_LINE root . right = newNode ( 2 ) NEW_LINE root . left . left = newNode ( 3 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE root . right . left = newNode ( 2 ) NEW_LINE root . right . left . right = newNode ( 1 ) NEW_LINE root . right . left . right . left = newNode ( 9 ) NEW_LINE print ( findMaxBends ( root ) - 1 ) NEW_LINE DEDENT