Binary Tree Longest Consecutive Sequence

How it works

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.

Steps

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.

Complexity

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

Where n is the number of nodes in the input tree

Things to watch for

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.

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.

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.

from typing import Optional

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

class Solution {
private:
    int maxLength = 0;

    int dfs(TreeNode* p) {
        if (p == nullptr) return 0;

        int L = dfs(p->left) + 1;
        int R = dfs(p->right) + 1;

        if (p->left != nullptr && p->val + 1 != p->left->val) {
            L = 1;
        }

        if (p->right != nullptr && p->val + 1 != p->right->val) {
            R = 1;
        }

        int length = max(L, R);
        maxLength = max(maxLength, length);

        return length;
    }

public:
    int longestConsecutive(TreeNode* root) {
        dfs(root);
        return maxLength;
    }
};