Longest Consecutive Sequence in Binary Tree

Longest Consecutive Sequence in Binary Tree

January 8, 2024
medium
DFS

Problem #

Given the root of 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 needs to be from parent to child (cannot be the reverse).

Example: # 

   1
    \
     3
    / \
   2   4
        \
         5

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

Solution #

The problem can be solved using depth-first search (DFS). We will traverse the tree and at each node, we will pass down the current sequence length and the expected value if the sequence is to continue.

Algorithm Steps: #

  1. Define a helper function that takes a node, its parent’s value, and the length of the current consecutive sequence.
  2. If the current node is None, return the length of the consecutive sequence.
  3. If the current node’s value is one more than its parent’s value, increment the sequence length; otherwise, reset it to 1.
  4. Recursively call the helper function for the left and right child, and return the maximum of the current sequence length and the returned lengths from the children.

Code in Python: # 

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def longestConsecutive(root):
    def dfs(node, parent_val, length):
        if not node:
            return length
        length = length + 1 if node.val == parent_val + 1 else 1
        left_length = dfs(node.left, node.val, length)
        right_length = dfs(node.right, node.val, length)
        return max(length, left_length, right_length)

    if not root:
        return 0
    return dfs(root, root.val - 1, 0)

# Example Usage
root = TreeNode(1, None, TreeNode(3, TreeNode(2), TreeNode(4, None, TreeNode(5))))
print(longestConsecutive(root))  # Output: 3

Time Complexity: #

O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity: #

O(H), where H is the height of the tree. This space is used for the recursion stack. In the worst case (a skewed tree), the space complexity could be O(N).

This problem showcases a practical use of DFS in a binary tree to solve a non-trivial problem related to node values and their relationships.