Binary Tree Longest Consecutive Sequence - Leetcode Solution

The problem statement

Given the root of a binary tree, return the length of the longest consecutive sequence path.

A consecutive sequence path refers to a sequence of integers where the absolute difference between any two adjacent nodes is 1. This sequence can start at any node in the tree and follow the parent-child connections.

Example:

Input: [1,null,3,2,4,null,null,null,5] Output: 3 Explanation: Longest consecutive sequence path is [3, 2, 1] or [1, 2, 3].

Approach

In this problem, we need to find the longest consecutive sequence path in a binary tree. A binary tree consists of nodes, where each node has a value, left child, and right child. To solve this problem, we will traverse the binary tree using DFS (depth-first search) algorithm and perform the following steps:

• We will keep track of three variables: current node, current consecutive sequence length, and the longest consecutive sequence length.
• During traversal, we will check if the current node value is consecutive to its parent node value. If yes, we will update the current consecutive sequence length and the longest consecutive sequence length.
• If the current node value is not consecutive to its parent node value, we will reset the current consecutive sequence length to 1.

Solution

Here's the code to solve the problem in Python:

""" 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: def dfs(node, parent_val, current_length, max_length): if not node: return max_length

        if node.val == parent_val + 1:
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 1
            
        max_length = dfs(node.left, node.val, current_length, max_length)
        max_length = dfs(node.right, node.val, current_length, max_length)
        
        return max_length
    
    if not root:
        return 0
    
    return dfs(root, root.val-1, 0, 1)

Explanation

• Our solution begins by defining a helper function dfs.
• We pass four arguments to the function: node is the current node, parent_val is the value of the parent node, current_length is the length of the current consecutive sequence, and max_length is the maximum consecutive sequence length found so far.
• We first check if the current node is None. If it is, we simply return the max_length variable.
• We then check if the current node value is consecutive to its parent node value. If it is, we increment the current_length variable and check if it is greater than the max_length variable. If it is, we update the max_length variable.
• If the current node value is not consecutive to its parent node value, we reset the current_length variable to 1.
• Finally, we recursively call the dfs function for the left and right subtree of the current node and update the max_length variable.
• After the dfs function returns, we return the max_length variable as the final result.
• In our main function longestConsecutive, we first check if the root node is None. If it is, we simply return 0.
• We then call the dfs function with the root node, parent value of root node minus 1, current_length of 0, and max_length of 1.
• We return the result returned by dfs function as the answer.

Time and Space Complexity

In our solution, we are traversing the binary tree once using DFS. Therefore, the time complexity of the solution is O(n), where n is the number of nodes in the binary tree.

In terms of space complexity, our solution uses the recursive stack space for the DFS traversal. Therefore, the space complexity of the solution is O(h), where h is the height of the binary tree. Since a binary tree can be skewed, the worst-case space complexity can be O(n).

1