298. Binary Tree Longest Consecutive Sequence - Explanation

Description

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

A consecutive sequence path is a path where the values increase by one along the path.

Note that the path can start at any node in the tree, and you cannot go from a node to its parent in the path.

Example 1:

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

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input: root = [2,null,3,2,null,1]

Output: 2

Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴].
-3 * 10⁴ <= Node.val <= 3 * 10⁴

Company Tags

1. Top Down Depth-first Search

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.max_length = 0
        self.dfs(root, None, 0)
        return self.max_length
    
    def dfs(self, p: TreeNode, parent: TreeNode, length: int) -> None:
        if p is None:
            return
        
        length = length + 1 if parent is not None and p.val == parent.val + 1 else 1
        self.max_length = max(self.max_length, length)
        
        self.dfs(p.left, p, length)
        self.dfs(p.right, p, length)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the number of nodes in the input tree

2. Bottom Up Depth-first Search

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.max_length = 0
        self.dfs(root)
        return self.max_length
    
    def dfs(self, p: Optional[TreeNode]) -> int:
        if p is None:
            return 0
        
        L = self.dfs(p.left) + 1
        R = self.dfs(p.right) + 1
        
        if p.left is not None and p.val + 1 != p.left.val:
            L = 1
        
        if p.right is not None and p.val + 1 != p.right.val:
            R = 1
        
        length = max(L, R)
        self.max_length = max(self.max_length, length)
        
        return length

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the number of nodes in the input tree