Maximum Consecutive Increasing Path Length in Binary Tree

In the realm of data structures and algorithms, binary trees are a fundamental concept. One interesting problem that can be explored with binary trees is finding the maximum consecutive increasing path length. This problem involves traversing a binary tree and determining the longest sequence of nodes where each subsequent node has a value greater than the previous one. In this blog, we'll delve into the details of this problem, understand the common approaches, and see some examples.

Table of Contents#

  1. Problem Statement
  2. Approaches to Solve
    • Brute Force Approach
    • Dynamic Programming (Memoization) Approach
  3. Common Practices and Best Practices
  4. Example Usage
  5. References

1. Problem Statement#

Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent - child connections. The longest consecutive path need not be from the root node or to a leaf node, but it must be strictly increasing.

For example, consider the following binary tree:

    1
     \
      3
     / \
    2   4
         \
          5

The longest consecutive increasing path is 3 → 4 → 5, and its length is 3.

2. Approaches to Solve#

Brute Force Approach#

Idea#

The brute - force approach involves performing a depth - first search (DFS) on each node of the binary tree. For each node, we check its left and right children. If the child's value is one more than the current node's value, we continue the search from that child. We keep track of the maximum length found during these searches.

Code Example (Python)#

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def longestConsecutive(root):
    if not root:
        return 0
    max_length = 1
 
    def dfs(node, current_length):
        nonlocal max_length
        max_length = max(max_length, current_length)
        if node.left:
            if node.left.val == node.val + 1:
                dfs(node.left, current_length + 1)
            else:
                dfs(node.left, 1)
        if node.right:
            if node.right.val == node.val + 1:
                dfs(node.right, current_length + 1)
            else:
                dfs(node.right, 1)
 
    dfs(root, 1)
    return max_length

Complexity Analysis#

  • Time Complexity: $O(n^2)$ in the worst case. For example, in a skewed tree (a tree that is like a linked list), for each node, we may have to traverse a long path again.
  • Space Complexity: $O(n)$ due to the recursion stack in the worst case (for a skewed tree).

Dynamic Programming (Memoization) Approach#

Idea#

We can use memoization to store the length of the longest consecutive increasing path starting from each node. For a given node, if we know the lengths of the longest consecutive paths from its left and right children (when they are consecutive), we can update the maximum length.

Code Example (Python)#

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def longestConsecutive(root):
    if not root:
        return 0
    max_length = 1
    memo = {}
 
    def dfs(node):
        nonlocal max_length
        if node not in memo:
            left_length = dfs(node.left) if node.left else 0
            right_length = dfs(node.right) if node.right else 0
            current_length = 1
            if node.left and node.left.val == node.val + 1:
                current_length = max(current_length, left_length + 1)
            if node.right and node.right.val == node.val + 1:
                current_length = max(current_length, right_length + 1)
            memo[node] = current_length
            max_length = max(max_length, current_length)
        return memo[node]
 
    dfs(root)
    return max_length

Complexity Analysis#

  • Time Complexity: $O(n)$ because each node is visited exactly once.
  • Space Complexity: $O(n)$ due to the recursion stack (in the worst case for a skewed tree) and the memoization dictionary.

3. Common Practices and Best Practices#

  • Input Validation: Always check if the root of the binary tree is None at the beginning of the function, as it can lead to null pointer exceptions (in languages like Java or C++) or AttributeError (in Python) if not handled.
  • Recursion Depth: Be aware of the recursion depth. In some programming languages (like Python), there is a default recursion limit. If dealing with very large trees, you may need to increase the recursion limit (but this is not always the best practice; iterative approaches may be better in such cases).
  • Code Readability: Use descriptive variable names. For example, in the above code, using max_length and current_length makes the code more understandable than using single - letter variables.

4. Example Usage#

# Create the binary tree from the example
root = TreeNode(1)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(5)
 
print(longestConsecutive(root))

This code will output 3, which is the length of the longest consecutive increasing path 3 → 4 → 5.

5. References#

  • LeetCode Problem: Longest Consecutive Sequence
  • "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. This book provides a comprehensive introduction to algorithm design and analysis, which is useful for understanding the complexity analysis of the above approaches.
2026-07