5.25 Binary Tree Longest Consecutive Sequence

5.25.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 298
• Difficulty: Medium
• URL: https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
• Tags:
• Techniques: Depth First Search, Tree

5.25.2 Description

Find the length of the longest path where consecutive nodes differ by +1.

5.25.3 Solution - DFS Tracking

5.25.3.1 Walkthrough

DFS down the tree while carrying the current consecutive length and the parent value. If the current node extends the sequence (node.val == parent.val + 1), increment the length; otherwise reset to 1. Track the maximum over all paths.

5.25.3.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

5.25.3.3 Code - Java

public int longestConsecutive(TreeNode root) {
    return dfs(root, null, 0);
}

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