Longest Path with Same Values in a Binary Tree | Function to print the longest path of same values ; Recursive calls to check for subtrees ; Variables to store maximum lengths in two directions ; If curr node and it 's left child has same value  ; If curr node and it 's right child has same value  ; Driver function to find length of longest same value path ; Helper function that allocates a new node with the given data and None left and right pointers . ; Driver code ; Let us construct a Binary Tree 4 / \ 4 4 / \ \ 4 9 5
def length ( node , ans ) : NEW_LINE INDENT if ( not node ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT left = length ( node . left , ans ) NEW_LINE right = length ( node . right , ans ) NEW_LINE Leftmax = 0 NEW_LINE Rightmax = 0 NEW_LINE if ( node . left and node . left . val == node . val ) : NEW_LINE INDENT Leftmax += left + 1 NEW_LINE DEDENT if ( node . right and node . right . val == node . val ) : NEW_LINE INDENT Rightmax += right + 1 NEW_LINE DEDENT ans [ 0 ] = max ( ans [ 0 ] , Leftmax + Rightmax ) NEW_LINE return max ( Leftmax , Rightmax ) NEW_LINE DEDENT def longestSameValuePath ( root ) : NEW_LINE INDENT ans = [ 0 ] NEW_LINE length ( root , ans ) NEW_LINE return ans [ 0 ] NEW_LINE DEDENT class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . val = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = newNode ( 4 ) NEW_LINE root . left = newNode ( 4 ) NEW_LINE root . right = newNode ( 4 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 9 ) NEW_LINE root . right . right = newNode ( 5 ) NEW_LINE print ( longestSameValuePath ( root ) ) NEW_LINE DEDENT