Problem Description

You are given the root of a binary tree and need to find the length of the longest consecutive path in the tree.

A consecutive path consists of nodes where each consecutive pair of nodes has values that differ by exactly 1. The path can be either increasing (like [1,2,3,4]) or decreasing (like [4,3,2,1]). Mixed patterns like [1,2,4,3] are not valid consecutive paths.

The key aspect of this problem is that the path doesn't have to follow the traditional parent-to-child direction. Instead, it can go through any connected nodes in the tree, including paths that go child-parent-child. This means a valid path could start from a node in the left subtree, go up through the parent, and continue down into the right subtree, as long as the values remain consecutive.

For example, if you have a tree structure where a parent node has value 2, its left child has value 1, and its right child has value 3, then the path [1,2,3] going from left child through parent to right child would be a valid consecutive path of length 3.

The task is to find the maximum length among all such possible consecutive paths in the tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where each node has at most two children and there are no cycles.

DFS

• Since we're dealing with a tree structure, the flowchart leads us directly to DFS (Depth-First Search).

Why DFS is the right choice:

• We need to explore all possible paths in the tree to find the longest consecutive sequence
• The path can go through child-parent-child relationships, requiring us to track information from subtrees
• We need to return information from children to parents (increasing and decreasing consecutive counts)
• DFS allows us to process each subtree completely before moving to the next, which is perfect for aggregating path information

Conclusion: The flowchart correctly identifies that for a tree-based problem like finding the longest consecutive path, DFS is the appropriate algorithm. The solution uses DFS to traverse the tree, maintaining both increasing and decreasing consecutive counts at each node, and combining them to find the maximum path length that could pass through that node.

Intuition

The key insight is that any consecutive path passing through a node can be broken down into two parts: an increasing sequence and a decreasing sequence that meet at that node.

Think about it this way - if we're standing at a node with value 5, a consecutive path through this node could look like [3,4,5,6,7]. This is essentially two segments: [3,4,5] (increasing to reach 5) and [5,6,7] (decreasing from 5's perspective, since child values are larger). The node with value 5 acts as a "bridge" connecting these two segments.

For each node, we need to track two pieces of information:

1. The longest increasing consecutive path ending at this node (coming from its children)
2. The longest decreasing consecutive path ending at this node (coming from its children)

Why track both? Because when we look at a parent node, what was "increasing" from a child's perspective becomes part of a different pattern. If a child has value 4 and parent has value 5, the child's increasing path contributes to the parent's decreasing path (since 4 + 1 = 5).

The brilliant part is combining these two counts at each node. If a node has an increasing path of length i and a decreasing path of length d, the maximum consecutive path passing through this node has length i + d - 1 (we subtract 1 because the node itself is counted in both paths).

This approach naturally handles the child-parent-child traversal requirement. When we compute the maximum path at each node by combining its increasing and decreasing sequences, we're essentially considering paths that go from one subtree, through the current node, and into another subtree - exactly what the problem asks for.

By using DFS to process each node bottom-up, we ensure that when we process a parent, we already have the complete information about the best consecutive paths in its children, allowing us to make optimal decisions at each step.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS approach where each node returns a pair [incr, decr] representing the maximum increasing and decreasing consecutive paths ending at that node.

Base Case: When we encounter a None node, we return [0, 0] since there's no path through an empty node.

Recursive Processing: For each node, we:

1. Initialize both incr and decr to 1 (the node itself forms a path of length 1)
2. Recursively process left and right children to get their [incr, decr] values

Connecting with Left Child: If the left child exists:

• If root.left.val + 1 == root.val: The left child's value is one less than current, so we can extend the left child's increasing path through current node. Set incr = i1 + 1
• If root.left.val - 1 == root.val: The left child's value is one more than current, so we can extend the left child's decreasing path through current node. Set decr = d1 + 1

Connecting with Right Child: If the right child exists:

• If root.right.val + 1 == root.val: Take the maximum of current incr and i2 + 1 (in case both children can form increasing paths)
• If root.right.val - 1 == root.val: Take the maximum of current decr and d2 + 1 (in case both children can form decreasing paths)

Updating Global Maximum: At each node, we calculate the longest path passing through it as incr + decr - 1. This represents:

• An increasing path from one subtree to current node (length incr)
• A decreasing path from current node to another subtree (length decr)
• Subtracting 1 because the current node is counted in both

We update the global ans variable with the maximum value seen so far.

Return Value: Each recursive call returns [incr, decr] to its parent, allowing the parent to potentially extend these consecutive paths further up the tree.

The final answer is the maximum path length found across all nodes in the tree.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this binary tree:

       2
      / \
     1   3

Step 1: Process leaf node 1

• Node value: 1
• No children, so initialize incr = 1, decr = 1
• Maximum path through this node: 1 + 1 - 1 = 1
• Update global ans = 1
• Return [1, 1] to parent

Step 2: Process leaf node 3

• Node value: 3
• No children, so initialize incr = 1, decr = 1
• Maximum path through this node: 1 + 1 - 1 = 1
• Global ans remains 1
• Return [1, 1] to parent

Step 3: Process root node 2

• Node value: 2
• Initialize incr = 1, decr = 1
• Left child returns [1, 1], right child returns [1, 1]

Connecting with left child (value 1):

• Check: 1 + 1 = 2 ✓ (left child is one less than current)
• This extends an increasing path: incr = 1 + 1 = 2
• Check: 1 - 1 = 0 ≠ 2 (no decreasing path)

Connecting with right child (value 3):

• Check: 3 + 1 = 4 ≠ 2 (no increasing path)
• Check: 3 - 1 = 2 ✓ (right child is one more than current)
• This extends a decreasing path: decr = 1 + 1 = 2

Calculate maximum path through node 2:

• incr = 2 (path: 1→2)
• decr = 2 (path: 2→3)
• Maximum path: 2 + 2 - 1 = 3
• This represents the complete path: 1→2→3
• Update global ans = 3

Final Result: The longest consecutive path has length 3, representing the sequence [1,2,3] that goes from the left child, through the parent, to the right child.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree.

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the algorithm performs constant time operations:

• Checking if left and right children exist
• Comparing values between parent and children nodes
• Updating the incr and decr counters
• Computing the maximum value for ans

Since we visit each node once and perform O(1) operations at each node, the overall time complexity is O(n).

Space Complexity: O(h) where h is the height of the binary tree.

The space complexity is determined by:

1. Recursion call stack: The DFS traversal uses recursion, and the maximum depth of the recursion stack equals the height of the tree. In the worst case (skewed tree), this could be O(n), while in the best case (balanced tree), it would be O(log n).

2. Auxiliary space: The algorithm uses only a constant amount of extra variables (incr, decr, ans, i1, d1, i2, d2) at each recursive call, which doesn't affect the overall space complexity.

Therefore, the space complexity is O(h), which ranges from O(log n) for a balanced tree to O(n) for a completely unbalanced tree.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing Path Direction with Value Direction

A common mistake is misunderstanding the relationship between the path direction (increasing/decreasing) and how it connects through parent-child relationships. Many developers incorrectly assume:

• An "increasing path" means going from parent to child with increasing values
• A "decreasing path" means going from parent to child with decreasing values

The Reality: The terms "increasing" and "decreasing" refer to the consecutive sequence values, not the tree traversal direction. When processing a node:

• If child.val + 1 == parent.val, the child contributes to an increasing path ending at parent
• If child.val - 1 == parent.val, the child contributes to a decreasing path ending at parent

Example of the Confusion:

# WRONG interpretation
if node.left and node.left.val == node.val + 1:  # This seems "increasing"
    increasing_length = left_increasing + 1  # But this would be wrong!

Correct Understanding:

# CORRECT: When left child is ONE LESS than parent
if node.left and node.left.val + 1 == node.val:
    increasing_length = left_increasing + 1  # Extends increasing path through parent

Pitfall 2: Not Handling Both Children Properly

Another mistake is using simple assignment instead of max() when both children could contribute to the same type of path:

Wrong Approach:

if node.right and node.right.val + 1 == node.val:
    increasing_length = right_increasing + 1  # This overwrites left child's contribution!

Correct Approach:

if node.right and node.right.val + 1 == node.val:
    increasing_length = max(increasing_length, right_increasing + 1)  # Keeps the better path

Pitfall 3: Forgetting to Subtract 1 When Calculating Path Through Node

When calculating the total path length passing through a node, developers often forget that the current node is counted in both the increasing and decreasing segments:

Wrong:

max_length = max(max_length, increasing_length + decreasing_length)  # Counts node twice!

Correct:

max_length = max(max_length, increasing_length + decreasing_length - 1)  # Accounts for overlap

Solution to Avoid These Pitfalls:

1. Draw out examples: Trace through small examples manually, labeling each node with its [incr, decr] values
2. Think from child's perspective: When at a parent node, think "what value must my child have for me to extend its path?"
3. Test edge cases: Single node tree, all same values, strictly increasing/decreasing paths
4. Verify the math: Always remember that joining two paths through a node means that node appears in both counts