LeetCode 549: Binary Tree Longest Consecutive Sequence II

Problem Restatement

We are given the root of a binary tree.

We need to find the length of the longest consecutive path.

A path can move from parent to child or child to parent, as long as the path stays connected.

The consecutive values may either:

• increase by 1
• decrease by 1

The path may change direction once at a node.

For example:

1 - 2 - 3

is valid because values increase consecutively.

Also:

3 - 2 - 1

is valid because values decrease consecutively.

Even:

1 - 2 - 1

is valid as a connected path, but it is not strictly consecutive in one direction through the center according to the required rules.

The important detail is that the path does not need to start at the root.

The official problem allows increasing and decreasing consecutive sequences, and the path may go child-parent-child. (leetcode.com)

Input and Output

Function shape:

def longestConsecutive(root: Optional[TreeNode]) -> int:
    ...

Examples

Consider:

    2
   / \
  1   3

The path:

1 -> 2 -> 3

is consecutive increasing.

The length is:

3

So the answer is:

3

Another example:

      3
     / \
    2   4
   /
  1

One longest path is:

1 -> 2 -> 3 -> 4

Length:

4

Now consider:

    2
   /
  3

The path:

3 -> 2

is decreasing consecutive.

The answer is:

2

First Thought: Track Increasing Paths Only

A simpler related problem asks only for increasing sequences downward from parent to child.

But this problem is harder because:

1. The sequence may increase or decrease.
2. The path may pass through a node.
3. One side may decrease while the other side increases.

Example:

1 -> 2 -> 3

At node 2:

• left side contributes decreasing
• right side contributes increasing

So we need to combine information from both children.

Key Insight

For every node, we need two values:

Suppose we are at node x.

If:

child.val == x.val + 1

then the child extends an increasing path.

If:

child.val == x.val - 1

then the child extends a decreasing path.

The longest path through the current node can combine:

decreasing side + current node + increasing side

For example:

1 -> 2 -> 3

At node 2:

• decreasing length from left = 2
• increasing length from right = 2

Combined path length:

2 + 2 - 1 = 3

We subtract 1 because the current node is counted twice.

Algorithm

Use DFS.

For each node:

1. Recursively compute (inc, dec) from the left child.
2. Recursively compute (inc, dec) from the right child.
3. Initialize:

inc = 1
dec = 1

4. If a child continues an increasing sequence:
   • update inc
5. If a child continues a decreasing sequence:
   • update dec
6. Update the global answer using:

inc + dec - 1

7. Return (inc, dec) for the current node.

Correctness

For every node, the DFS computes:

• inc: the longest increasing consecutive path starting at that node and moving downward
• dec: the longest decreasing consecutive path starting at that node and moving downward

These values are correct by recursion.

Suppose a child value equals:

node.val + 1

Then the child continues an increasing consecutive sequence from the current node. So the current node can extend the child’s increasing path by one.

Similarly, if:

child.val == node.val - 1

then the child continues a decreasing sequence from the current node.

The longest valid path passing through the current node combines one decreasing branch and one increasing branch. The current node connects those two directions.

The combined length is:

inc + dec - 1

because the current node belongs to both paths and would otherwise be counted twice.

Every valid consecutive path in the tree has some highest turning node where the increasing and decreasing parts meet. When DFS processes that node, the algorithm evaluates the corresponding combined length.

Therefore, the global maximum found by the algorithm is the length of the longest consecutive path in the tree.

Complexity

Let n be the number of nodes.

h is the height of the tree.

Worst case:

O(n)

Balanced tree:

O(log n)

Implementation

# 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

from typing import Optional

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

        def dfs(node: Optional[TreeNode]) -> tuple[int, int]:
            nonlocal answer

            if node is None:
                return (0, 0)

            inc = 1
            dec = 1

            if node.left:
                left_inc, left_dec = dfs(node.left)

                if node.left.val == node.val + 1:
                    inc = max(inc, left_inc + 1)

                elif node.left.val == node.val - 1:
                    dec = max(dec, left_dec + 1)

            if node.right:
                right_inc, right_dec = dfs(node.right)

                if node.right.val == node.val + 1:
                    inc = max(inc, right_inc + 1)

                elif node.right.val == node.val - 1:
                    dec = max(dec, right_dec + 1)

            answer = max(answer, inc + dec - 1)

            return (inc, dec)

        dfs(root)
        return answer

Code Explanation

For each node, we start with:

inc = 1
dec = 1

A single node itself forms a path of length 1.

Then we recursively process the left child:

left_inc, left_dec = dfs(node.left)

If the left child is one larger:

node.left.val == node.val + 1

then the current node extends an increasing path:

inc = max(inc, left_inc + 1)

If the left child is one smaller:

node.left.val == node.val - 1

then the current node extends a decreasing path:

dec = max(dec, left_dec + 1)

The same logic applies to the right child.

Then we combine both directions:

answer = max(answer, inc + dec - 1)

This checks the longest path passing through the current node.

Finally, we return:

(inc, dec)

for use by the parent.

Small Walkthrough

Tree:

    2
   / \
  1   3

At node 1:

inc = 1
dec = 1

At node 3:

inc = 1
dec = 1

At node 2:

Left child:

1 == 2 - 1

So:

dec = 2

Right child:

3 == 2 + 1

So:

inc = 2

Combined:

2 + 2 - 1 = 3

Answer becomes:

3

Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert s.longestConsecutive(root) == 3

    root = TreeNode(
        3,
        TreeNode(
            2,
            TreeNode(1),
            None,
        ),
        TreeNode(4),
    )
    assert s.longestConsecutive(root) == 4

    root = TreeNode(2, TreeNode(3))
    assert s.longestConsecutive(root) == 2

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

    root = TreeNode(
        2,
        TreeNode(1),
        TreeNode(2),
    )
    assert s.longestConsecutive(root) == 2

    print("all tests passed")

run_tests()