1. Top Down Depth-first Search

Intuition

We traverse the tree from root to leaves, passing down the current consecutive sequence length to each child. At each node, we check if it continues the sequence from its parent (value is exactly one more than the parent). If so, we extend the sequence; otherwise, we start a new sequence. We track the maximum length seen across all nodes.

Algorithm

1. Initialize a global variable to track the maximum consecutive sequence length.
2. Define a DFS function that takes the current node, its parent, and the current sequence length.
3. If the current node is null, return.
4. If the current node's value equals the parent's value plus 1, increment the length; otherwise, reset it to 1.
5. Update the maximum length with the current length.
6. Recursively call DFS on both children, passing the current node as the parent.
7. Return the maximum length found.

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.max_length = 0
        self.dfs(root, None, 0)
        return self.max_length
    
    def dfs(self, p: TreeNode, parent: TreeNode, length: int) -> None:
        if p is None:
            return
        
        length = length + 1 if parent is not None and p.val == parent.val + 1 else 1
        self.max_length = max(self.max_length, length)
        
        self.dfs(p.left, p, length)
        self.dfs(p.right, p, length)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the number of nodes in the input tree

---

2. Bottom Up Depth-first Search

Intuition

Instead of passing information down, we can compute the consecutive sequence length from leaves up to the root. Each node returns the length of the longest consecutive sequence starting from itself going downward. The parent then checks if it can extend this sequence by verifying that its value is exactly one less than its child's value.

Algorithm

1. Initialize a global variable to track the maximum consecutive sequence length.
2. Define a DFS function that returns the longest consecutive sequence starting from the current node.
3. If the current node is null, return 0.
4. Recursively get the sequence lengths from left and right children, adding 1 for the current node.
5. If the left child exists but doesn't form a consecutive sequence (current value + 1 != left value), reset the left length to 1.
6. Similarly check and potentially reset the right length.
7. Update the maximum length with the larger of the two lengths.
8. Return the larger length to the parent.

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.max_length = 0
        self.dfs(root)
        return self.max_length
    
    def dfs(self, p: Optional[TreeNode]) -> int:
        if p is None:
            return 0
        
        L = self.dfs(p.left) + 1
        R = self.dfs(p.right) + 1
        
        if p.left is not None and p.val + 1 != p.left.val:
            L = 1
        
        if p.right is not None and p.val + 1 != p.right.val:
            R = 1
        
        length = max(L, R)
        self.max_length = max(self.max_length, length)
        
        return length

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the number of nodes in the input tree

---

Common Pitfalls

Allowing Decreasing Sequences

The problem asks for strictly increasing consecutive sequences where each child is exactly parent.val + 1. A common mistake is checking for any consecutive values (including decreasing) or allowing gaps.

# Wrong: allows decreasing sequences
if abs(p.val - parent.val) == 1:

Not Resetting Length When Sequence Breaks

When the consecutive pattern breaks, the length must reset to 1 (the current node starts a new sequence). Forgetting to reset causes incorrect counts.

# Wrong: continues accumulating instead of resetting
length = length + 1  # should be: length = 1 when pattern breaks

Forgetting to Handle the Root Node

The root node has no parent, so attempting to check parent.val without a null check causes errors. The root always starts a new sequence of length 1.