Problem Description

The "Binary Tree Longest Consecutive Sequence" problem asks you to find the length of the longest consecutive sequence in a binary tree. A consecutive sequence is defined as a path where each child node has a value exactly one greater than its parent node. The path must go from parent to child (downwards), and can start and end at any node in the tree.

• The tree is made up of nodes, each with an integer value.
• You can only move from parent to child (not in reverse).
• The sequence must be strictly consecutive (e.g., 3-4-5, not 3-5-6).
• The answer should be the length of the longest such path in the tree.
• Each node can be used only once in a path.

Example:
Given this tree:

        1
         \
          3
         / \
        2   4
             \
              5
    

Thought Process

The problem is about finding a path in a binary tree where each next node is exactly one greater than its parent. The naive (brute-force) approach would be to try all possible paths from every node, but this is inefficient.

Instead, we can use a recursive approach: for each node, check if it continues a consecutive sequence from its parent. If yes, increase the current path length; if not, reset the path length to 1. At each node, keep track of the maximum length found so far.

This problem is a classic example of using Depth-First Search (DFS) traversal of a tree, where we pass information (current sequence length and previous node value) down the recursion.

Solution Approach

To solve the problem efficiently, we'll use a recursive DFS traversal. Here's a step-by-step breakdown:

1. Define a helper function that takes the current node, the value of its parent, and the current length of the consecutive sequence.
2. Base case: If the node is null, return.
3. Check for consecutiveness: If the current node's value is exactly one more than the parent's value, increment the current length; otherwise, reset it to 1.
4. Update the result: At each step, update a variable tracking the maximum path length found so far.
5. Recursive calls: Recurse for both left and right children, passing the current node's value and the updated length.
6. Start the recursion: Begin from the root node, with an initial parent value that cannot be part of a sequence (e.g., root.val - 1).

This approach ensures that every path is explored only once, and we always know the current sequence length.

Example Walkthrough

Let's walk through the sample tree:

        1
         \
          3
         / \
        2   4
             \
              5
    

1. Start at node 1: no parent, so length is 1.
2. Go right to 3: 3 != 1+1, so length resets to 1.
3. Left child of 3 is 2: 2 != 3+1, length stays 1.
4. Right child of 3 is 4: 4 == 3+1, length is now 2.
5. Right child of 4 is 5: 5 == 4+1, length increases to 3.
6. No more children; the maximum length found is 3 (the sequence 3-4-5).

Time and Space Complexity

• Brute-force approach: For each node, you might try all paths starting from that node, leading to exponential time complexity in the worst case (O(N^2) or worse).
• Optimized DFS approach: Each node is visited once, and each recursive call does constant work, so the time complexity is O(N), where N is the number of nodes.
• Space complexity: O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), this could be O(N).

Summary

The Binary Tree Longest Consecutive Sequence problem is best solved with a recursive DFS approach, passing the current sequence length and previous value down the tree. This method is both intuitive and efficient, requiring only a single pass through the tree and minimal extra space. The key insight is to update the sequence length only when the consecutive property holds, and always keep track of the maximum found so far.

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        self.max_len = 0

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

        dfs(root, root.val - 1 if root else 0, 0)
        return self.max_len
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution {
public:
    int maxLen = 0;
    void dfs(TreeNode* node, int parentVal, int length) {
        if (!node) return;
        if (node->val == parentVal + 1)
            length += 1;
        else
            length = 1;
        maxLen = std::max(maxLen, length);
        dfs(node->left, node->val, length);
        dfs(node->right, node->val, length);
    }
    int longestConsecutive(TreeNode* root) {
        if (!root) return 0;
        dfs(root, root->val - 1, 0);
        return maxLen;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

class Solution {
    private int maxLen = 0;

    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        dfs(root, root.val - 1, 0);
        return maxLen;
    }

    private void dfs(TreeNode node, int parentVal, int length) {
        if (node == null) return;
        if (node.val == parentVal + 1)
            length++;
        else
            length = 1;
        maxLen = Math.max(maxLen, length);
        dfs(node.left, node.val, length);
        dfs(node.right, node.val, length);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var longestConsecutive = function(root) {
    let maxLen = 0;

    function dfs(node, parentVal, length) {
        if (!node) return;
        if (node.val === parentVal + 1) {
            length += 1;
        } else {
            length = 1;
        }
        maxLen = Math.max(maxLen, length);
        dfs(node.left, node.val, length);
        dfs(node.right, node.val, length);
    }

    if (root) {
        dfs(root, root.val - 1, 0);
    }
    return maxLen;
};