Problem statement

https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

Solution

Just traverse our tree with dfs (or bfs), where dfs(node) is the longest consecutive sequence for given node. Each time run dfs for left and right subtrees, and then update result for node, so we have postorder traversal here.

Complexity

Time complexity is $O(n)$, space complexity is $O(h)$.

Code

class Solution:
    def longestConsecutive(self, root):
        self.ans = 0
        
        def dfs(node):
            out = 1
            
            for child in [node.left, node.right]:
                if not child: continue
                cand = dfs(child)
                if child.val == node.val + 1:
                    out = max(cand + 1, out)
            self.ans = max(out, self.ans)
            return out
        
        dfs(root)
        return self.ans