Binary Tree Longest Consecutive Sequence

Problem Statement

We are given the root of a binary tree, and we need to identify the length of the longest consecutive sequence path within this tree. A consecutive sequence path is characterized by adjacent nodes along the path having increasing values by exactly one unit as one progresses. This path can originate from any node within the tree, yet it is essential to note that backtracking from a node to its parent is disallowed during the path formation.

Examples

Example 1

Input:

root = [1,null,3,2,4,null,null,null,5]

Output:

3

Explanation:

Longest consecutive sequence path is 3-4-5, so return 3.

Example 2

Input:

root = [2,null,3,2,null,1]

Output:

2

Explanation:

Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

Constraints

• The number of nodes in the tree is in the range [1, 3 * 104].
• -3 * 104 <= Node.val <= 3 * 104

Approach and Intuition

To solve this problem, let's delve into the examples and constraints to gain a clearer intuition of our approach:

Intuition:

• A path might begin at any node, and it continues as long as subsequent node values increment by one. The complexity arises from the fact that a node in a binary tree has up to two children and the longest path can diverge through either.

Approach:

1. Utilize a depth-first search (DFS). As we traverse, keep a count of the sequence length.
2. At each node:
   • If the node is a continuation of a consecutive sequence (i.e., node value is parent node value + 1), then increment the current sequence length.
   • If not, reset the sequence length for the current path to 1.
3. Recursively apply the DFS on the left and right children of the current node, passing the updated sequence length.
4. The final answer is the maximum path length found during the traversal.

From the Examples:

Example 1:

Input:

root = [1,null,3,2,4,null,null,null,5]

• Here, three nodes (3-4-5) increment consecutively, offering a maximum sequence length of 3.

Example 2:

Input:

root = [2,null,3,2,null,1]

• The path 2-3 is valid, providing a maximum sequence length of 2.

Constraints Considerations:

• With node values ranging broadly from -3 * 104 to 3 * 104 and up to 3 * 104 nodes, we must design an efficient recursive DFS function that maintains the continuity of the sequence and avoids unnecessary calculations.

This binary tree based traversal coupled with conditional checks to maintain consecutive sequence integrity provides a way to deduce the longest increasing consecutive sequence efficiently.

Solutions

private int maxLen = 0;

public int longestSequence(TreeNode node) {
    traverse(node);
    return maxLen;
}

private int traverse(TreeNode n) {
    if (n == null) return 0;
    int leftLen = traverse(n.left) + 1;
    int rightLen = traverse(n.right) + 1;
    if (n.left != null && n.val + 1 != n.left.val) {
        leftLen = 1;
    }
    if (n.right != null && n.val + 1 != n.right.val) {
        rightLen = 1;
    }
    int curLength = Math.max(leftLen, rightLen);
    maxLen = Math.max(maxLen, curLength);
    return curLength;
}