We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Longest Consecutive Sequence

Number: 298

Difficulty: Medium

Paid? Yes

Companies: Walmart Labs, Google

Problem Description

Given the root of a binary tree, return the length of the longest consecutive sequence path. A consecutive sequence path is defined as a path where each node's value is exactly one more than its parent's value. The path can start at any node in the tree, but you can only travel from parent to child.

Key Insights

  • Use a Depth-First Search (DFS) to traverse the binary tree.
  • Pass the current node’s value and the length of the current consecutive sequence in the recursive call.
  • When a node’s value is exactly one greater than its parent’s value, increment the sequence length; otherwise, reset it to 1.
  • Keep track of the maximum sequence length found during the traversal.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, since each node is visited once.
Space Complexity: O(H), where H is the height of the tree. In the worst-case of a skewed tree, the recursion stack can be O(N).

Solution

The solution involves using DFS to explore every node in the binary tree while keeping track of the length of the consecutive sequence. For each node, if the node's value is one greater than its parent’s value, we increment the sequence length; otherwise, we reset the sequence length to 1. During the traversal, a global variable is updated if the current sequence length exceeds the previously recorded maximum. This approach ensures that every possible consecutive path is considered.

Code Solutions

# 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:
        # Initialize a variable to keep track of the maximum sequence length.
        self.max_length = 0
        
        # Helper function to perform DFS traversal.
        def dfs(node, parent_val, current_length):
            if not node:
                return
            # Check if the current node's value is consecutive.
            if node.val == parent_val + 1:
                current_length += 1
            else:
                current_length = 1
            # Update the maximum sequence length found so far.
            self.max_length = max(self.max_length, current_length)
            # Recursively traverse the left and right children.
            dfs(node.left, node.val, current_length)
            dfs(node.right, node.val, current_length)
        
        # Start DFS with an initial condition that forces the first node to count.
        dfs(root, root.val - 1, 0)
        return self.max_length
← Back to All Questions