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 II

Number: 549

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given the root of a binary tree, return the length of the longest consecutive path in the tree. A consecutive path is one where the values of directly connected nodes differ by one. The path can be either increasing or decreasing, and it can change direction (child-parent-child) as long as the consecutive requirement holds.

Key Insights

  • Use Depth-First Search (DFS) to visit every node.
  • For each node, compute:
    • The longest increasing consecutive path starting from that node.
    • The longest decreasing consecutive path starting from that node.
  • Combine the increasing and decreasing paths (subtracting one to avoid double counting the current node) to potentially form a longer consecutive sequence through the node.
  • Update a global maximum to record the longest path seen.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes since every node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

Solution

The solution employs a DFS traversal. At every node, we calculate two values:

  1. inc – the length of the longest increasing consecutive sequence starting from that node.
  2. dec – the length of the longest decreasing consecutive sequence starting from that node.

For each child of the current node:

  • If the child's value is node.val + 1, update the increasing sequence.
  • If the child's value is node.val - 1, update the decreasing sequence.

Then, the longest path through the current node is inc + dec - 1 (subtracting one to avoid counting the current node twice). A global variable maintains the maximum length encountered. This process works regardless of the path direction because it combines both increasing and decreasing parts.

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 global maximum path length variable
        self.max_length = 0
        
        def dfs(node):
            if not node:
                return (0, 0)  # (increasing, decreasing)
            
            inc = dec = 1  # Each node counts as length 1
            
            # Process left child
            if node.left:
                left_inc, left_dec = dfs(node.left)
                # If left child's value is consecutive increasing with respect to node
                if node.left.val == node.val + 1:
                    inc = max(inc, left_inc + 1)
                # If left child's value is consecutive decreasing with respect to node
                elif node.left.val == node.val - 1:
                    dec = max(dec, left_dec + 1)
            
            # Process right child
            if node.right:
                right_inc, right_dec = dfs(node.right)
                # If right child's value is consecutive increasing with respect to node
                if node.right.val == node.val + 1:
                    inc = max(inc, right_inc + 1)
                # If right child's value is consecutive decreasing with respect to node
                elif node.right.val == node.val - 1:
                    dec = max(dec, right_dec + 1)
            
            # Update the global maximum path by combining increasing and decreasing paths
            self.max_length = max(self.max_length, inc + dec - 1)
            return (inc, dec)
        
        dfs(root)
        return self.max_length
← Back to All Questions