LeetCode 298: Binary Tree Longest Consecutive Sequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 298: Binary Tree Longest Consecutive Sequence?

In LeetCode 298: Binary Tree Longest Consecutive Sequence, you’re given the root of a binary tree where each node has an integer value. Your task is to find the length of the longest path where each node’s value is exactly 1 more than its parent’s, moving downward (e.g., 1 → 2 → 3 is length 3). The path doesn’t need to start at the root or pass through it—it can be anywhere in the tree. For example, in [1,null,3,2,4,null,null,null,5], the longest sequence is 3 → 4 → 5 (length 3). This problem tests your tree traversal skills, sharing a vibe with LeetCode 124: Binary Tree Maximum Path Sum.

Problem Statement

• Input: A binary tree root.
• Output: An integer—the length of the longest consecutive increasing sequence.
• Rules: Sequence increases by 1 (e.g., 1 → 2); path is parent-to-child; can start anywhere.

Constraints

• Tree nodes: 0 to 10⁴.
• Node values: 1 to 10⁵.

Examples

• Input: root = [1,null,3,2,4,null,null,null,5]
• Output: 3 (3 → 4 → 5)
• Input: root = [2,null,3,2,null,1]
• Output: 2 (2 → 3 or 2 → 1)
• Input: root = [1]
• Output: 1

Understanding the Problem: Chasing the Streak

To solve LeetCode 298: Binary Tree Longest Consecutive Sequence in Python, we need to find the longest chain of nodes where each child’s value is the parent’s value plus 1, like a ladder going up. For [1,null,3,2,4], we check paths like 1 → 2 (length 2) or 3 → 4 (length 2), but also 3 → 4 → 5 (length 3) elsewhere. The path can start anywhere, so we need to explore every node. We’ll use:

• Best Solution (DFS with Parent Tracking): O(n) time, O(h) space—fast and sleek.
• Alternative Solution (BFS with Level Tracking): O(n) time, O(w) space—structured but bulkier.

Let’s dive into the DFS solution with a friendly breakdown that’s easy to follow.

Best Solution: DFS with Parent Tracking

Why This Is the Best Solution

The DFS with parent tracking is the top choice for LeetCode 298 because it’s efficient—O(n) time to visit each node once, O(h) space (h = tree height)—and uses a simple recursive approach to track sequences. It passes the parent’s value and current streak length down the tree, updating a global max as it goes. It’s like climbing each branch, counting steps up, and keeping the longest climb—perfect for this problem!

How It Works

Let’s imagine this like hiking through the tree:

• Step 1: Start at Each Node:
• Visit every node with DFS (root, left, right).
• Step 2: Track the Streak:
• For each node, know its parent’s value and how long the streak is so far.
• If current value = parent + 1, streak grows by 1; else, reset to 1.
• Step 3: Update the Max:
• Keep a global max length, updated at each node with the current streak.
• Step 4: Why It Works:
• DFS explores all paths downward, catching every possible sequence.
• Parent tracking checks the +1 rule without extra storage.
• Global max ensures we don’t miss a streak starting anywhere.

It’s like counting ladder rungs as you climb—track and compare!

Step-by-Step Example

Example: root = [1,null,3,2,4,null,null,null,5]

• Start: max_len = 1 (single node minimum).
• Node 1 (parent=None, len=1):
• No parent, len=1.
• Right: 3 (parent=1, len=1).
• Node 3 (parent=1, len=1):
• 3 ≠ 1+1, reset len=1.
• Left: 2 (parent=3, len=1).
• Right: 4 (parent=3, len=1).
• Node 2 (parent=3, len=1):
• 2 ≠ 3+1, len=1, max_len=1.
• Node 4 (parent=3, len=1):
• 4 = 3+1, len=2.
• Right: 5 (parent=4, len=2).
• Node 5 (parent=4, len=2):
• 5 = 4+1, len=3.
• No kids, max_len=3.
• Result: 3 (longest streak: 3 → 4 → 5).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy code# 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

class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        # Step 1: Keep a global max length
        self.max_len = 1

        # Step 2: Helper to explore with parent and length
        def dfs(node, parent_val, curr_len):
            if not node:  # No node, stop
                return

            # Step 3: Check if consecutive with parent
            if parent_val is not None and node.val == parent_val + 1:
                curr_len += 1  # Streak continues
            else:
                curr_len = 1  # Reset streak

            # Step 4: Update max length
            self.max_len = max(self.max_len, curr_len)

            # Step 5: Explore kids
            dfs(node.left, node.val, curr_len)
            dfs(node.right, node.val, curr_len)

        # Step 6: Start from root
        dfs(root, None, 1)
        return self.max_len

• Line 12: Set a class variable max_len to track the longest streak, starting at 1 (single node).
• Line 15-24: Helper dfs:
• Line 16-17: If node is None, stop.
• Line 19-22: If parent exists and node.val = parent + 1, grow curr_len; else reset to 1.
• Line 24: Update max_len with current streak.
• Line 26-27: Recurse to left and right, passing node’s value as parent and current length.
• Line 29-30: Start DFS from root with no parent (None) and length 1.

• Time Complexity: O(n)—visits each node once.
• Space Complexity: O(h)—recursion stack (h = tree height).

This is like a tree hike—count steps up and keep the best!

Alternative Solution: BFS with Level Tracking

Why an Alternative Approach?

BFS with level tracking uses a queue to explore level-by-level—O(n) time, O(w) space (w = max width). It tracks each node’s streak by pairing it with its parent’s value and length, like a structured walk across the tree. It’s bulkier but shows a different angle, less common for this problem but insightful.

How It Works

Let’s think of this as a level-by-level stroll:

• Step 1: Queue nodes with parent value and streak length.
• Step 2: For each node, check if it continues the streak from its parent.
• Step 3: Update max length and queue kids.

It’s like checking floors of a building for ladders!

Step-by-Step Example

Example: root = [1,null,3,2,4,null,null,null,5]

• Queue: [(1, None, 1)], max_len = 1.
• Node 1:
• No parent, len=1.
• Queue: [(3, 1, 1)].
• Node 3:
• 3 ≠ 1+1, len=1.
• Queue: [(2, 3, 1), (4, 3, 1)].
• Node 2: len=1, max_len=1.
• Node 4:
• 4 = 3+1, len=2.
• Queue: [(5, 4, 2)].
• Node 5:
• 5 = 4+1, len=3, max_len=3.
• Result: 3.

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        if not root:
            return 0

        max_len = 1
        queue = deque([(root, None, 1)])  # (node, parent_val, length)

        while queue:
            node, parent_val, curr_len = queue.popleft()
            if parent_val is not None and node.val == parent_val + 1:
                curr_len += 1
            else:
                curr_len = 1
            max_len = max(max_len, curr_len)
            if node.left:
                queue.append((node.left, node.val, curr_len))
            if node.right:
                queue.append((node.right, node.val, curr_len))

        return max_len

• Time Complexity: O(n)—visits each node.
• Space Complexity: O(w)—queue size (w = max width).

It’s a broad sweep but heavier!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n) time, O(h) space, sleek recursion.
• Cons: Recursive depth.
• BFS (Alternative):
• Pros: O(n) time, O(w) space, level clarity.
• Cons: Wider space use.

DFS wins for efficiency.

Additional Examples and Edge Cases

• []: 0.
• [1,2]: 2.
• [2,1]: 1.

DFS is faster.

Complexity Breakdown

• DFS: Time O(n), Space O(h).
• BFS: Time O(n), Space O(w).

DFS rules.

Key Takeaways

• DFS: Dive deep—fast!
• BFS: Spread wide—clear!
• Trees: Sequences are fun.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Climb That Streak

LeetCode 298: Binary Tree Longest Consecutive Sequence in Python is a neat tree adventure. DFS tracks streaks efficiently, while BFS maps them out. Want more? Try LeetCode 124: Binary Tree Maximum Path Sum or LeetCode 687: Longest Univalue Path. Ready to count? Head to Solve LeetCode 298 on LeetCode and find that longest streak today!