LeetCode 549 - Binary Tree Longest Consecutive Sequence II

LeetCode Problem 549

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

Solution

Problem Understanding

This problem asks us to find the length of the longest consecutive sequence path in a binary tree. Unlike the simpler version of the problem where the sequence must move strictly downward from parent to child, this version allows the path to move in a child-parent-child direction as well.

A consecutive path means that adjacent nodes differ by exactly 1. The sequence can either be increasing or decreasing.

For example:

• 1 -> 2 -> 3 -> 4 is valid because each value increases by 1
• 4 -> 3 -> 2 -> 1 is also valid because each value decreases by 1
• 1 -> 2 -> 4 -> 3 is invalid because 2 and 4 differ by 2

The important detail is that the path does not need to follow only downward edges. A valid path may pass through a parent node and continue into another subtree. For example:

    2
   / \
  1   3

The longest valid path here is:

1 -> 2 -> 3

This path changes direction at the root.

The input is the root node of a binary tree. Each node contains:

• an integer value
• a left child pointer
• a right child pointer

The output is a single integer representing the maximum length of any valid consecutive path.

The constraints are important:

• Up to 3 * 10^4 nodes
• Node values range from -3 * 10^4 to 3 * 10^4

Since the tree can contain tens of thousands of nodes, any solution worse than linear time may become too slow. This strongly suggests that we should process each node only once.

Several edge cases are important:

• A tree with only one node, answer should be 1
• Completely increasing chains
• Completely decreasing chains
• Paths that switch direction through a parent
• Trees with duplicate values
• Trees where no consecutive relationship exists
• Skewed trees with depth close to 3 * 10^4

A naive implementation may miss paths that combine both left and right subtrees through the current node.

Approaches

Brute Force Approach

A brute force strategy would try every node as a starting point and explore all possible consecutive paths from that node.

For every node, we could recursively search:

• increasing sequences
• decreasing sequences
• paths extending through ancestors and descendants

This quickly becomes complicated because valid paths may bend at a parent node. To fully explore all possibilities, we would repeatedly traverse overlapping portions of the tree.

The brute force approach is correct because it explicitly enumerates all candidate paths and checks whether consecutive conditions hold. However, it performs excessive repeated work.

In the worst case, for every node we may traverse a large portion of the tree again, leading to quadratic complexity.

Optimal DFS Dynamic Programming Approach

The key insight is that each node only needs to know two things from its children:

• the longest increasing consecutive path starting at this node
• the longest decreasing consecutive path starting at this node

If a child value is:

• node.val + 1, then the child can extend an increasing sequence
• node.val - 1, then the child can extend a decreasing sequence

Once we know the best increasing and decreasing lengths from both children, we can combine them through the current node.

For example:

1 <- 2 -> 3

At node 2:

• decreasing path from left = 2 -> 1
• increasing path from right = 2 -> 3

These combine into:

1 -> 2 -> 3

with total length:

decreasing + increasing - 1

We subtract 1 because the current node gets counted twice.

This leads naturally to a postorder DFS where each node computes its contribution using already computed child information.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly explores overlapping paths
Optimal	O(n)	O(h)	Single DFS traversal with dynamic programming

Here, n is the number of nodes and h is the tree height.

Algorithm Walkthrough

1. Start a depth first traversal from the root.
2. For each node, recursively compute results from the left and right children before processing the current node. This is a postorder traversal because the current node depends on child information.
3. At every node, maintain two values:

• increasing, the longest increasing consecutive path starting at this node
• decreasing, the longest decreasing consecutive path starting at this node

Initially, both values are 1 because the node itself forms a valid path of length 1. 4. Process the left child:

• If left.val == node.val + 1, then the current node can extend an increasing sequence through the left child.
• If left.val == node.val - 1, then the current node can extend a decreasing sequence through the left child.

5. Process the right child similarly.
6. After updating both increasing and decreasing lengths, compute the best path passing through the current node:

increasing + decreasing - 1

This combines both directions into one valid consecutive path. 7. Update a global maximum answer if this combined length is larger than the current best. 8. Return (increasing, decreasing) to the parent so higher nodes can continue extending these sequences.

Why it works

For every node, the algorithm computes the longest increasing and decreasing paths that start at that node. Since every valid consecutive path must pass through some highest node where the direction may change, combining increasing and decreasing lengths at every node guarantees that all valid paths are considered exactly once. The DFS ensures that child information is fully computed before parents depend on it.

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

from typing import Optional, Tuple

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

        def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:
            if not node:
                return (0, 0)

            increasing = 1
            decreasing = 1

            left_inc, left_dec = dfs(node.left)
            right_inc, right_dec = dfs(node.right)

            if node.left:
                if node.left.val == node.val + 1:
                    increasing = max(increasing, 1 + left_inc)
                elif node.left.val == node.val - 1:
                    decreasing = max(decreasing, 1 + left_dec)

            if node.right:
                if node.right.val == node.val + 1:
                    increasing = max(increasing, 1 + right_inc)
                elif node.right.val == node.val - 1:
                    decreasing = max(decreasing, 1 + right_dec)

            self.answer = max(
                self.answer,
                increasing + decreasing - 1
            )

            return (increasing, decreasing)

        dfs(root)
        return self.answer

The implementation uses a recursive helper function dfs that returns two integers for every node.

The first integer represents the longest increasing path beginning at the current node. The second integer represents the longest decreasing path beginning at the current node.

The recursion processes children first because the parent depends on child information to extend sequences correctly.

Each node begins with:

increasing = 1
decreasing = 1

because the node alone forms a valid sequence of length 1.

When examining children:

• If the child is exactly +1, we extend the increasing sequence.
• If the child is exactly -1, we extend the decreasing sequence.

After processing both children, the algorithm combines both directions:

increasing + decreasing - 1

This represents a path that may travel from one subtree, through the current node, into another subtree.

The global variable self.answer stores the maximum path length found anywhere in the tree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func longestConsecutive(root *TreeNode) int {
    answer := 0

    var dfs func(node *TreeNode) (int, int)

    dfs = func(node *TreeNode) (int, int) {
        if node == nil {
            return 0, 0
        }

        increasing := 1
        decreasing := 1

        leftInc, leftDec := dfs(node.Left)
        rightInc, rightDec := dfs(node.Right)

        if node.Left != nil {
            if node.Left.Val == node.Val+1 {
                if 1+leftInc > increasing {
                    increasing = 1 + leftInc
                }
            } else if node.Left.Val == node.Val-1 {
                if 1+leftDec > decreasing {
                    decreasing = 1 + leftDec
                }
            }
        }

        if node.Right != nil {
            if node.Right.Val == node.Val+1 {
                if 1+rightInc > increasing {
                    increasing = 1 + rightInc
                }
            } else if node.Right.Val == node.Val-1 {
                if 1+rightDec > decreasing {
                    decreasing = 1 + rightDec
                }
            }
        }

        current := increasing + decreasing - 1
        if current > answer {
            answer = current
        }

        return increasing, decreasing
    }

    dfs(root)

    return answer
}

The Go implementation follows the same logic as the Python version. Since Go does not support tuple return values directly, the recursive function returns two integers.

Go uses nil checks instead of Python's None.

The global answer is maintained through a closure variable captured by the recursive function.

Integer overflow is not a concern because the maximum path length is bounded by the number of nodes, which is at most 3 * 10^4.

Worked Examples

Example 1

    1
   / \
  2   3

Expected output:

2

Step by Step Trace

Node	Increasing	Decreasing	Combined Path	Global Answer
2	1	1	1	1
3	1	1	1	1
1	2	1	2	2

Explanation:

• Node 2 has no children, so both values are 1

• Node 3 also has values (1,1)

• At node 1:

• Left child 2 = 1 + 1, increasing becomes 2

• Right child 3 differs by 2, ignored

• Best path length becomes 2

Example 2

    2
   / \
  1   3

Expected output:

3

Step by Step Trace

Node	Increasing	Decreasing	Combined Path	Global Answer
1	1	1	1	1
3	1	1	1	1
2	2	2	3	3

Explanation:

At node 2:

• Left child 1 = 2 - 1

• decreasing becomes 2

• Right child 3 = 2 + 1

• increasing becomes 2

Combined:

2 + 2 - 1 = 3

This forms the valid path:

1 -> 2 -> 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is processed exactly once
Space	O(h)	Recursive call stack height

The algorithm performs a single DFS traversal. Every node computes constant work using information from its children, so the total runtime is linear in the number of nodes.

The auxiliary space comes from recursion depth. In a balanced tree this is O(log n), while in the worst case of a skewed tree it becomes O(n).

Test Cases

# Definition for testing
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):
        self.answer = 0

        def dfs(node):
            if not node:
                return (0, 0)

            increasing = 1
            decreasing = 1

            left_inc, left_dec = dfs(node.left)
            right_inc, right_dec = dfs(node.right)

            if node.left:
                if node.left.val == node.val + 1:
                    increasing = max(increasing, 1 + left_inc)
                elif node.left.val == node.val - 1:
                    decreasing = max(decreasing, 1 + left_dec)

            if node.right:
                if node.right.val == node.val + 1:
                    increasing = max(increasing, 1 + right_inc)
                elif node.right.val == node.val - 1:
                    decreasing = max(decreasing, 1 + right_dec)

            self.answer = max(
                self.answer,
                increasing + decreasing - 1
            )

            return (increasing, decreasing)

        dfs(root)
        return self.answer

sol = Solution()

# Example 1
root = TreeNode(1, TreeNode(2), TreeNode(3))
assert sol.longestConsecutive(root) == 2  # simple increasing edge

# Example 2
root = TreeNode(2, TreeNode(1), TreeNode(3))
assert sol.longestConsecutive(root) == 3  # child-parent-child path

# Single node
root = TreeNode(5)
assert sol.longestConsecutive(root) == 1  # minimum tree size

# Increasing chain
root = TreeNode(1,
    TreeNode(2,
        TreeNode(3,
            TreeNode(4))))
assert sol.longestConsecutive(root) == 4  # strictly increasing

# Decreasing chain
root = TreeNode(4,
    TreeNode(3,
        TreeNode(2,
            TreeNode(1))))
assert sol.longestConsecutive(root) == 4  # strictly decreasing

# Mixed direction through root
root = TreeNode(3,
    TreeNode(2,
        TreeNode(1)),
    TreeNode(4,
        None,
        TreeNode(5)))
assert sol.longestConsecutive(root) == 5  # full path through root

# No consecutive values
root = TreeNode(10,
    TreeNode(20),
    TreeNode(30))
assert sol.longestConsecutive(root) == 1  # no valid edges

# Duplicate values
root = TreeNode(2,
    TreeNode(2),
    TreeNode(2))
assert sol.longestConsecutive(root) == 1  # duplicates do not count

# Negative values
root = TreeNode(-1,
    TreeNode(-2),
    TreeNode(0))
assert sol.longestConsecutive(root) == 3  # handles negatives correctly

# Uneven tree
root = TreeNode(5,
    TreeNode(4,
        TreeNode(3),
        None),
    TreeNode(6))
assert sol.longestConsecutive(root) == 4  # combines both sides

Test	Why
[1,2,3]	Validates simple parent-child consecutive paths
[2,1,3]	Validates child-parent-child combination
Single node	Confirms minimum answer is 1
Increasing chain	Tests pure increasing sequences
Decreasing chain	Tests pure decreasing sequences
Mixed direction tree	Verifies combining left and right subtrees
No consecutive values	Ensures invalid edges are ignored
Duplicate values	Confirms equal values are not consecutive
Negative values	Verifies logic works for negative integers
Uneven tree	Tests asymmetric subtree handling

Edge Cases

Single Node Tree

A tree containing only one node is the smallest valid input. A buggy implementation might incorrectly return 0 because there are no edges. The correct answer is 1 because a single node itself forms a valid consecutive path. The implementation handles this by initializing both increasing and decreasing lengths to 1.

Duplicate Values

Nodes with equal values are not consecutive because consecutive numbers must differ by exactly 1. For example:

2
|
2

should not extend any sequence. The implementation explicitly checks only:

child.val == node.val + 1

or

child.val == node.val - 1

so duplicates are automatically ignored.

Paths That Change Direction

The most important edge case is when the longest path passes through a parent node and combines both subtrees:

1 -> 2 -> 3

A naive top-down DFS may only track increasing or decreasing sequences independently and miss this combination. The implementation solves this by maintaining both increasing and decreasing lengths at every node and combining them with:

increasing + decreasing - 1

This guarantees that turning paths are counted correctly.

Skewed Trees

A completely skewed tree behaves like a linked list and may reach depth 3 * 10^4. Recursive solutions can approach recursion depth limits in Python. Algorithmically, the solution still works correctly because each node is processed once. The space complexity becomes O(n) in this worst case due to recursion stack usage.