Binary Tree Longest Consecutive Sequence

Intuition

Because a consecutive path only ever moves downward, we can decide how long the run is at a node using just its parent's value. As we descend we carry two pieces of information: the value the current node would need in order to continue the run, and the length of the run so far. If the node matches the expected value, the run grows by one; if it does not, the run restarts at length one beginning at this node. Every node updates a shared best, and both children are explored with the next expected value being node.val + 1. Visiting each node once with constant work per node makes this a clean linear-time solution.

Algorithm walkthrough

1. 1Keep a shared best initialized to 0.
2. 2Call dfs(root, root.val, 0) so the root matches its own expected value and starts a run of length 1.
3. 3At each node, if node.val equals the expected target, increment length; otherwise reset length to 1.
4. 4Update best = max(best, length).
5. 5Recurse into left and right children with target = node.val + 1 and the current length.
6. 6Return best once the traversal completes.

Implementation

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.best = 0

        def dfs(node, target, length):
            if not node:
                return
            if node.val == target:
                length += 1
            else:
                length = 1
            self.best = max(self.best, length)
            dfs(node.left, node.val + 1, length)
            dfs(node.right, node.val + 1, length)

        if root:
            dfs(root, root.val, 0)
        return self.best