LeetCode 298: Binary Tree Longest Consecutive Sequence

Problem Restatement

We are given the root of a binary tree.

We need to return the length of the longest consecutive sequence path.

A consecutive path means each next node has value exactly one greater than its parent.

For example:

3 -> 4 -> 5

is valid.

But:

3 -> 2 -> 1

is not valid, because the values decrease.

The path can start at any node, but it must go downward from parent to child. We cannot go from a child back to its parent. The constraints say the tree has at least one node and at most 3 * 10^4 nodes.

Input and Output

Function shape:

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

Examples

For:

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

The tree is:

    1
     \
      3
     / \
    2   4
         \
          5

The longest consecutive path is:

3 -> 4 -> 5

So the answer is:

3

For:

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

The tree is:

    2
     \
      3
     /
    2
   /
  1

The path:

2 -> 3

has length 2.

The path:

3 -> 2 -> 1

does not count because it decreases. So the answer is:

2

These examples match the source statement.

First Thought: Check Every Starting Node

A direct approach is to try every node as the start of a path.

From each node, we follow children whose value is exactly one greater.

Then we keep the maximum length found.

This is correct, but it can repeat work. A subtree may be explored many times from different ancestors.

We can compute the answer in one DFS instead.

Key Insight

During DFS, carry the length of the current consecutive path.

When we visit a child, compare it with its parent:

child.val == parent.val + 1

If this is true, the child continues the current path.

If this is false, the child starts a new path of length 1.

So each node only needs two pieces of information from its parent:

We update a global answer with the best length seen anywhere.

Algorithm

Use DFS.

At each node:

1. If the node continues the sequence from its parent, increment the length.
2. Otherwise, reset the length to 1.
3. Update the answer.
4. Recurse into the left child.
5. Recurse into the right child.

The path may start at any node because whenever a node does not continue its parent, we reset the length to 1.

Correctness

At each node, the DFS stores the length of the longest valid consecutive path that ends at that node and follows the current root-to-node traversal path.

If the node value is exactly one more than the parent value, then the current node extends the previous valid path, so increasing the length by one is correct.

If the node value does not continue the parent, then no valid consecutive path ending at this node can include the parent. The best path ending here starts at this node, so its length is 1.

The algorithm updates the global answer at every node. Since every valid downward consecutive path ends at some node, that path length is considered when DFS visits its final node.

Therefore, after all nodes are visited, the global answer is the longest consecutive downward path in the whole tree.

Complexity

Let n be the number of nodes and h be the tree height.

For a balanced tree, h = O(log n).

For a skewed tree, h = O(n).

Implementation

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

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

        def dfs(node, parent_value, length):
            nonlocal answer

            if node is None:
                return

            if node.val == parent_value + 1:
                length += 1
            else:
                length = 1

            answer = max(answer, length)

            dfs(node.left, node.val, length)
            dfs(node.right, node.val, length)

        dfs(root, root.val - 1, 0)

        return answer

Code Explanation

We store the best length found so far:

answer = 0

The DFS receives the current node, the parent value, and the length of the current path before this node:

def dfs(node, parent_value, length):

If the current node is missing, there is nothing to process:

if node is None:
    return

If the current node continues the sequence:

if node.val == parent_value + 1:
    length += 1

we extend the path.

Otherwise:

else:
    length = 1

the current node starts a new path.

Then we update the global best answer:

answer = max(answer, length)

Finally, we recurse into both children:

dfs(node.left, node.val, length)
dfs(node.right, node.val, length)

The initial call uses:

dfs(root, root.val - 1, 0)

so the root always starts with length 1.

Testing

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def test_longest_consecutive():
    s = Solution()

    root = TreeNode(1)
    root.right = TreeNode(3)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(5)

    assert s.longestConsecutive(root) == 3

    root = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(2)
    root.right.left.left = TreeNode(1)

    assert s.longestConsecutive(root) == 2

    root = TreeNode(10)
    assert s.longestConsecutive(root) == 1

    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.left.left = TreeNode(4)

    assert s.longestConsecutive(root) == 4

    root = TreeNode(4)
    root.left = TreeNode(3)
    root.left.left = TreeNode(2)

    assert s.longestConsecutive(root) == 1

    print("all tests passed")

test_longest_consecutive()

Test meaning: