Longest Increasing Path in Binary Tree

Given the root of a binary tree, find the length of the longest increasing path – a path can start at any node, and only goes downwards, i.e. it cannot stretch across subtrees and travel upwards.

           9
         /   \
       0*     10
      / \     /  \
     1   1*  0    1
    /.  / \        \
   3.  -2  3*       2
          /
         4*
       /  \
      -1.  0

Conditions

Remember that this path does not need to go through the root, so this function needs to be able to reset when it doesn’t meet the condition. We also want the longest path, so be able to return that.

Solution

Cache the previous value in prev_val, which starts at negative infinity. Use this to cache the parent’s value. If the current node’s value > prev_val, we can increment the length. When we dont have any nodes left, return the current length.

def traverse(node, prev_val=float('-inf'), curr_len=1):
  if not node:
    return curr_len
  if node.val > prev_val:
    return max(traverse(node.left, node.val, curr_len + 1), traverse(node.right, node.val, curr_len + 1))
  else:
    return traverse(node)

def main(root):
    if not root:
        return 0
    return traverse(root)