# 549. Binary Tree Longest Consecutive Sequence II

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

# Solution

Approach 1: returns (max_increasing, max_decreasing) for path through root while keeping a global max.

# Code (Python)

Approach 1: (not verified on leetcode)

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def longest_consecutive(root):
    max_length = [1]
    _explore(root, max_length)
    return max_length[0]

def _explore(root, max_length):
    # returns (max_increasing, max_decreasing) for path through root
    if not root:
        return (0, 0)
    left_increasing, left_decreasing = _explore(root.left, max_length)
    right_increasing, right_decreasing = _explore(root.right, max_length)
    increasing, decreasing = 1, 1
    if root.left:
        if root.left.val + 1 == root.val:
            decreasing += left_decreasing
        if root.left.val - 1 == root.val:
            increasing += left_increasing
    if root.right:
        if root.right.val + 1 == root.val:
            decreasing = max(decreasing, right_decreasing + 1)
        if root.right.val - 1 == root.val:
            increasing  = max(increasing, right_increasing + 1)
    max_length[0] = max(max_length[0], increasing, decreasing)
    if root.left and root.right:
        if root.left.val + 1 == root.val == root.right.val - 1:
            max_length[0] = max(max_length[0], left_decreasing + 1 + right_increasing)
        if root.right.val + 1 == root.val == root.left.val - 1:
            max_length[0] = max(max_length[0], left_increasing + 1 + right_decreasing)
    return (increasing, decreasing)

node = TreeNode(2, TreeNode(1), TreeNode(3))
root = TreeNode(5, node, TreeNode(6))
print(longest_consecutive(root))

Approach 2:

# Code (C++)

Approach 1:

Approach 2: