LeetCode 298 - Binary Tree Longest Consecutive Sequence

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to find the length of the longest consecutive sequence path in a binary tree, where a consecutive sequence path is defined as a path in which the values increase by exactly one from parent to child. The path must move downward, meaning from a node to its children, and cannot move back to the parent. The input is the root of a binary tree, which may contain up to 30,000 nodes, with values ranging from -30,000 to 30,000. The output is a single integer representing the maximum length of such a sequence anywhere in the tree.

Understanding the constraints helps guide the approach. The tree size is large enough that a brute-force solution examining every possible path from every node individually could be too slow. Edge cases to consider include a tree with only one node, trees where all nodes have the same value (no consecutive sequences), and trees with multiple branches that contain sequences of the same maximum length.

Approaches

A naive brute-force approach would attempt to start a traversal from every node, recursively finding the longest consecutive path from that node. While this is correct in principle, it has severe performance limitations because it revisits the same subtrees multiple times, resulting in repeated computation. Specifically, if there are n nodes, the time complexity can be as bad as O(n^2) in the worst case for a highly unbalanced tree.

The key insight for an optimal solution is to use a single depth-first search (DFS) traversal while carrying along the length of the consecutive sequence as we traverse. At each node, we compare the node value with its parent value to determine if the sequence continues. This way, every node is visited exactly once, avoiding redundant work, and we maintain a global maximum to track the longest sequence found so far.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Start DFS from every node, recomputing sequences in subtrees
Optimal	O(n)	O(h)	Single DFS, carrying sequence length, h = tree height (stack space)

Algorithm Walkthrough

Initialize a variable max_length to zero. This will track the length of the longest consecutive path found during traversal.
Define a helper DFS function that takes the current node, its parent value, and the current consecutive length.
At each node, compare the node's value to the parent value. If the node value equals the parent value plus one, increment the consecutive length. Otherwise, reset the consecutive length to 1 because a new sequence starts here.
Update max_length if the current consecutive length is greater than the previously recorded maximum.
Recursively call DFS for the left child and the right child, passing the current node's value as the new parent value and the updated consecutive length.
Begin the DFS traversal from the root node with an initial length of 0 and a parent value that cannot match any node (e.g., root value minus 1 or a sentinel).
Return max_length after the DFS completes.

Why it works: This works because every node is visited exactly once, and at each node, we correctly maintain the length of the consecutive sequence that includes that node. By passing the sequence length downwards, we do not need to recompute sequences for subtrees repeatedly, and tracking the maximum ensures we capture the longest sequence in the entire tree.

Python Solution

# 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: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        self.max_length = 0
        
        def dfs(node: Optional[TreeNode], parent_val: int, length: int) -> None:
            if not node:
                return
            if node.val == parent_val + 1:
                length += 1
            else:
                length = 1
            self.max_length = max(self.max_length, length)
            dfs(node.left, node.val, length)
            dfs(node.right, node.val, length)
        
        dfs(root, root.val - 1, 0)
        return self.max_length

In this Python implementation, we use a class variable self.max_length to maintain the global maximum. The DFS function updates the consecutive length depending on whether the current node continues the sequence. The traversal ensures every node is considered exactly once, making it efficient for large trees.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func longestConsecutive(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    maxLength := 0
    
    var dfs func(node *TreeNode, parentVal int, length int)
    dfs = func(node *TreeNode, parentVal int, length int) {
        if node == nil {
            return
        }
        if node.Val == parentVal+1 {
            length++
        } else {
            length = 1
        }
        if length > maxLength {
            maxLength = length
        }
        dfs(node.Left, node.Val, length)
        dfs(node.Right, node.Val, length)
    }
    
    dfs(root, root.Val-1, 0)
    return maxLength
}

The Go implementation mirrors the Python approach. We use a local variable maxLength and an inner recursive function dfs to traverse the tree. Handling nil is equivalent to checking for None in Python, and integers in Go can handle the given node value range without overflow concerns.

Worked Examples

Example 1: `[1,null,3,2,4,null,null,null,5]`

Traversal and sequence calculation:

Node	Parent	Length	Max
1	0	1	1
3	1	1	1
2	3	1	1
4	3	2	2
5	4	3	3

Longest sequence: 3-4-5, length = 3

Example 2: `[2,null,3,2,null,1]`

Node	Parent	Length	Max
2	1	1	1
3	2	2	2
2	3	1	2
1	2	1	2

Longest sequence: 2-3, length = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once during DFS
Space	O(h)	Call stack depth in DFS, where h is the height of the tree

The algorithm efficiently traverses the tree once, and only the call stack depth contributes to space complexity.

Test Cases

# Provided examples
assert Solution().longestConsecutive(TreeNode(1, None, TreeNode(3, TreeNode(2), TreeNode(4, None, TreeNode(5))))) == 3  # Example 1
assert Solution().longestConsecutive(TreeNode(2, None, TreeNode(3, TreeNode(2), None, TreeNode(1)))) == 2  # Example 2

# Single node tree
assert Solution().longestConsecutive(TreeNode(10)) == 1  # Single node, length = 1

# All nodes same value
assert Solution().longestConsecutive(TreeNode(5, TreeNode(5), TreeNode(5))) == 1  # No consecutive increments

# Left-skewed consecutive
assert Solution().longestConsecutive(TreeNode(1, TreeNode(2, TreeNode(3)))) == 3  # Left chain 1-2-3

# Right-skewed consecutive
assert Solution().longestConsecutive(TreeNode(3, None, TreeNode(4, None, TreeNode(5)))) == 3  # Right chain 3-4-5

Test	Why
Example 1	Validates tree with branching and longest sequence in right subtree
Example 2	Checks path not including all nodes
Single node	Ensures base case handled correctly
All nodes same	Ensures non-incrementing sequences are counted as length 1
Left-skewed	Validates sequence in a linear left path
Right-skewed	Validates sequence in a linear right path

Edge Cases

One edge case is a single-node tree. The longest consecutive sequence should correctly return 1 since the sequence consists of just that node. Another edge case is when all nodes have the same value. Any naive implementation that does not reset the sequence at non-consecutive nodes could mistakenly count longer sequences; our solution correctly resets the sequence length. A third important case is an unbalanced tree with long branches in only one direction. DFS ensures that each branch is considered individually, so the longest path is accurately found regardless of tree shape.