Binary Tree Longest Consecutive Sequence

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

Question

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

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example:

Input:
   1
    \
     3
    / \
   2   4
        \
         5
Output:3
Explanation:
Longest consecutive sequence path is 3-4-5, so return 3.


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

Analyzation

Recursion

Note that Consecutive means that the sub node should be the root node +1.

Steps:

• Create a helper function that holds the sub longest variable

• Recursively get the left subtree’s length and right subtree’s length

• If the child node is root node +1, update the sub longest variable to the max(previous sub longest, left+1) or (right+1) because the previous sub longest could be the opposite subtree’s.

• Update the longest variable to sub longest variable if sub longest is greater than the longest.

The Code

class Solution:
    """
    @param root: the root of binary tree
    @return: the length of the longest consecutive sequence path
    """
    
    def longestConsecutive(self, root):
        # write your code here
        self.longest = 0
        self.dfs(root)
        
        return self.longest
    
    def dfs(self, root):
        if root is None:
            return 0 
            
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        
        subLongest = 1
        
        if root.left:
            if root.val + 1 == root.left.val:
                subLongest = max(subLongest, left + 1)
        if root.right:
            if root.val + 1 == root.right.val:
                subLongest = max(subLongest, right + 1)
        
        if subLongest > self.longest:
            self.longest = subLongest
        
        return subLongest

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).