Binary Tree Longest Consecutive Sequence II

Problem Statement

The task involves determining the length of the longest consecutive path within a binary tree. By definition, a consecutive path refers to a sequence where the values of adjacent nodes differ by exactly one. Intriguingly, the order of the sequence could be ascending or descending; for instance, both [1,2,3,4] and [4,3,2,1] qualify as valid sequences. However, it's important to note that any deviation from a difference of one disrupts the consecutiveness, rendering sequences like [1,2,4,3] invalid. Additionally, the consecutive path can traverse beyond direct parent-child connections, possibly incorporating a child-parent-child traversal pattern.

Examples

Example 1

Input:

root = [1,2,3]

Output:

2

Explanation:

The longest consecutive path is [1, 2] or [2, 1].

Example 2

Input:

root = [2,1,3]

Output:

3

Explanation:

The longest consecutive path is [1, 2, 3] or [3, 2, 1].

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, we can utilize a recursive depth-first search (DFS) approach, which examines paths from each node to its children and then compares their values to determine if they form a part of a consecutive sequence. The recursive function will process each node and its corresponding child nodes to establish whether they form part of an ascending or descending consecutive sequence. Here’s a planned approach laid out step-by-step:

1. Implement a recursive function longest_consec_path(node) which:

   • Initializes two variables, increase and decrease, both set to 1 initially. These variables track the length of the increasing and decreasing consecutive paths respectively.
   • Checks the left child of the current node:
     • If the value of the left child is one less than the current node, increment the increase variable based on the result from further recursive calls.
     • If the value of the left child is one more than the current node, increment the decrease variable similarly.
   • Repeats the same checks for the right child of the current node.
   • Compares and updates a global variable that keeps track of the longest consecutive path found at any node.

2. After processing both child nodes:

   • Aggregate the results from both the left and right children to update the longest path recorded.

3. Execute this function starting from the root of the binary tree.

4. The key to this approach lies in effectively combining the increasing and decreasing sequences at every node to update the global maximum path length.

5. Edge cases:

   • If the tree is empty or consists of only one node, the longest consecutive path will be 0 and 1 respectively.

This technique ensures that every node and its possible contributions to a consecutive sequence (both in increasing and decreasing order) are considered, making it a comprehensive solution to identifying the longest consecutive path in a binary tree.

Solutions

public class Solution {
    int maximumLength = 0;
    
    public int findLongestConsecutive(TreeNode root) {
        calculateLongest(root);
        return maximumLength;
    }
    
    public int[] calculateLongest(TreeNode node) {
        if (node == null) {
            return new int[] {0, 0};
        }
    
        int increase = 1, decrease = 1;
        if (node.left != null) {
            int[] leftPath = calculateLongest(node.left);
            if (node.val == node.left.val + 1) {
                decrease = leftPath[1] + 1;
            } else if (node.val == node.left.val - 1) {
                increase = leftPath[0] + 1;
            }
        }
    
        if (node.right != null) {
            int[] rightPath = calculateLongest(node.right);
            if (node.val == node.right.val + 1) {
                decrease = Math.max(decrease, rightPath[1] + 1);
            } else if (node.val == node.right.val - 1) {
                increase = Math.max(increase, rightPath[0] + 1);
            }
        }
    
        maximumLength = Math.max(maximumLength, increase + decrease - 1);
        return new int[] {increase, decrease};
    }
}