# Python solution with detailed explanation

• Solution

Binary Tree Longest Consecutive Sequence https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

Bottom Up (Postfix) O(N) Approach

• Maintain a global variable to track the maximum path so far.
• Use bottom up approach to return the consecutive sequence count from both left and right nodes.
``````class Solution(object):
def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.max_so_far = 0
self.helper(root)
return self.max_so_far

def helper(self, root):
if root == None:
return 0
max_l, max_r = self.helper(root.left), self.helper(root.right)
max_curr = 1
if root.left and root.left.val == root.val+1:
max_curr = max(max_curr, max_l+1)
if root.right and root.right.val == root.val+1:
max_curr = max(max_curr, max_r+1)
self.max_so_far = max(max_curr, self.max_so_far)
return max_curr
``````

Top Down (Prefix) O(N) Approach

• Maintain a prev variable which tracks the value of the previous variable.
• Maintain a so_far variable that tracks the count of the current run.
• Update or reset so_far to 1 depending on if current and prev node satisfy the constraint.
``````class Solution(object):
def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
so_far, self.max_so_far, prev = 0, 0, None
self.helper(root, so_far, prev)
return self.max_so_far

def helper(self, root, so_far, prev):
if root == None:
return
elif (prev == None) or (prev+1 == root.val):
self.max_so_far = max(self.max_so_far, so_far+1)
so_far = so_far+1
else:
so_far = 1
self.helper(root.left, so_far, root.val)
self.helper(root.right, so_far, root.val)
return
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.