NUHMAN.com

Introduction

LeetCode 298: Binary Tree Longest Consecutive Sequence is a problem where you need to find the longest consecutive sequence path in a binary tree. The path must be such that each node's value is exactly one greater than its parent node's value.

This problem tests your ability to traverse a binary tree and find paths with specific conditions, such as consecutive increasing sequences, using tree traversal techniques like depth-first search (DFS).

Problem Statement

Given the root of a binary tree, return the length of the longest consecutive path in the binary tree. The path must be such that each node’s value is exactly one greater than its parent node’s value.

The path can be either upwards or downwards, but it must follow consecutive integer values.

Example

python

Input:
    1
   / \
  2   3
 /
4
Output:
3

Explanation: The longest consecutive sequence is `[1, 2, 3]`, which is the path starting from the root node `1` through its right child `3`.

✅ Step-by-Step Solution

🧠 Intuition

The key here is recognizing that we need to perform a depth-first search (DFS) to explore all possible paths in the binary tree. While exploring each node, we check if its value is exactly one greater than its parent’s value. If it is, we increment the length of the current consecutive sequence.

We keep track of the longest sequence found during the traversal.

✅ Approach

1. DFS Traversal:

• Perform a DFS traversal where at each node, we:
• Check if the current node is part of a consecutive sequence (i.e., its value is one greater than its parent's value).
• If it is, extend the current consecutive path.
• If it’s not, reset the current consecutive sequence to 1.

1. Recursive Approach:

• We use a recursive helper function to traverse the tree.
• For each node, calculate the longest consecutive sequence starting from that node, and return the result up the tree.

1. Return the Maximum Sequence:

• We maintain a global variable to track the maximum length of the consecutive sequence found during the DFS traversal.

✅ Python Code

python

class Solution:
    def longestConsecutive(self, root):
        """Returns the length of the longest consecutive sequence path in the binary tree."""
        
        def dfs(node, parent_val, current_length):
            if not node:
                return current_length
            
            # If the current node is consecutive, extend the path length
            if node.val == parent_val + 1:
                current_length += 1
            else:
                current_length = 1  # Reset the sequence
            
            # Recurse on left and right children
            left_length = dfs(node.left, node.val, current_length)
            right_length = dfs(node.right, node.val, current_length)
            
            # Return the longest sequence found so far
            return max(current_length, left_length, right_length)
        
        # Start DFS with the root node and an arbitrary parent value (e.g., -1)
        return dfs(root, float('-inf'), 0)

🧪 How It Works

1. DFS Function:

• The dfs function is a recursive function that traverses the binary tree. It takes:
• node: The current node being processed.
• parent_val: The value of the parent node.
• current_length: The length of the current consecutive sequence.
• For each node, we check if the value of the node is exactly one greater than the parent’s value. If it is, we increment the current_length. If not, we reset the current_length to 1.

1. Base Case:

• If a node is None (i.e., we've reached the end of a path), we return the current_length.

1. Recursive Call:

• We make recursive calls for both the left and right children of the node. Each recursive call continues the search for the longest consecutive sequence in the left and right subtrees.

1. Return the Result:

• At each node, we return the maximum of the current consecutive sequence (current_length), the length of the sequence in the left subtree (left_length), and the length of the sequence in the right subtree (right_length).

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n), where n is the number of nodes in the tree. Each node is visited exactly once.Space ComplexityO(h), where h is the height of the tree. This space is used by the recursion stack. In the worst case, the space complexity can be O(n) if the tree is unbalanced.

• Time Complexity: We visit each node once during the DFS traversal, so the time complexity is O(n), where n is the number of nodes in the tree.
• Space Complexity: The space complexity is determined by the recursion stack, which in the worst case is proportional to the height of the tree, O(h), where h is the height of the tree.

🔍 Edge Cases

1. Empty Tree:

• If the tree is empty (root is None), the longest consecutive sequence is 0.

1. Single Node:

• If the tree has only one node, the longest consecutive sequence is 1 because a single node by itself forms a valid consecutive sequence.

1. All Nodes with Consecutive Values:

• If all nodes in the tree form a consecutive sequence (e.g., each node's value is exactly one greater than its parent's value), the result will be the total number of nodes in the tree.

1. No Consecutive Nodes:

• If no nodes form a consecutive sequence (i.e., each node’s value is greater than the parent’s value by more than 1), the longest consecutive sequence is 1.

1. Unbalanced Tree:

• The algorithm works efficiently for both balanced and unbalanced trees.

✅ Conclusion

LeetCode 298: Binary Tree Longest Consecutive Sequence is a problem that challenges us to find the longest path of consecutive integers in a binary tree. Using a depth-first search (DFS) strategy, we efficiently traverse the tree while keeping track of consecutive sequences. By recursively calculating the longest path at each node, we can solve the problem in O(n) time.

This approach ensures that we handle edge cases like empty trees, single-node trees, and unbalanced trees efficiently.