Maximum Consecutive Increasing Path Length in Binary Tree | A binary tree node ; Returns the maximum consecutive path length ; Get the vlue of current node The value of the current node will be prev node for its left and right children ; If current node has to be a part of the consecutive path then it should be 1 greater thn the value of the previous node ; a ) Find the length of the left path b ) Find the length of the right path Return the maximum of left path and right path ; Find the length of the maximum path under subtree rooted with this node ; Take the maximum previous path and path under subtree rooted with this node ; A Wrapper over maxPathLenUtil ( ) ; Return 0 if root is None ; Else compute maximum consecutive increasing path length using maxPathLenUtil ; Driver program to test above function
class Node : NEW_LINE INDENT def __init__ ( self , val ) : NEW_LINE INDENT self . val = val NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def maxPathLenUtil ( root , prev_val , prev_len ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return prev_len NEW_LINE DEDENT curr_val = root . val NEW_LINE if curr_val == prev_val + 1 : NEW_LINE INDENT return max ( maxPathLenUtil ( root . left , curr_val , prev_len + 1 ) , maxPathLenUtil ( root . right , curr_val , prev_len + 1 ) ) NEW_LINE DEDENT newPathLen = max ( maxPathLenUtil ( root . left , curr_val , 1 ) , maxPathLenUtil ( root . right , curr_val , 1 ) ) NEW_LINE return max ( prev_len , newPathLen ) NEW_LINE DEDENT def maxConsecutivePathLength ( root ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return 0 NEW_LINE DEDENT return maxPathLenUtil ( root , root . val - 1 , 0 ) NEW_LINE DEDENT root = Node ( 10 ) NEW_LINE root . left = Node ( 11 ) NEW_LINE root . right = Node ( 9 ) NEW_LINE root . left . left = Node ( 13 ) NEW_LINE root . left . right = Node ( 12 ) NEW_LINE root . right . left = Node ( 13 ) NEW_LINE root . right . right = Node ( 8 ) NEW_LINE print " Maximum ▁ Consecutive ▁ Increasing ▁ Path ▁ Length ▁ is " , NEW_LINE print maxConsecutivePathLength ( root ) NEW_LINE