Problem

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.

Solution

Method 1 - Using BFS

Here is the approach:

  1. Initialization:
    • Use a queue to perform the BFS traversal. Each queue entry will store a node and the current length of the consecutive sequence path ending at that node.
  2. BFS Traversal:
    • For each node, check if it can form a consecutive sequence with its children. If it can, increment the sequence length; otherwise, reset the sequence length to 1.
  3. Track Maximum Length:
    • Keep a variable to track the maximum length of the consecutive sequence path encountered during the BFS traversal.

Code

Java
public class Solution {
    private class NodePair {
        TreeNode node;
        int length;

        NodePair(TreeNode node, int length) {
            this.node = node;
            this.length = length;
        }
    }
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int maxLength = 0;
        Queue<NodePair> queue = new LinkedList<>();
        queue.offer(new NodePair(root, 1));

        while (!queue.isEmpty()) {
            NodePair pair = queue.poll();
            TreeNode node = pair.node;
            int length = pair.length;

            maxLength = max(maxLength, length);

            if (node.left != null) {
                if (node.left.val == node.val + 1) {
                    queue.offer(new NodePair(node.left, length + 1));
                } else {
                    queue.offer(new NodePair(node.left, 1));
                }
            }

            if (node.right != null) {
                if (node.right.val == node.val + 1) {
                    queue.offer(new NodePair(node.right, length + 1));
                } else {
                    queue.offer(new NodePair(node.right, 1));
                }
            }
        }

        return maxLength;
    }
}
Python
from collections import deque

class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        if not root:
            return 0

        max_length = 0
        queue = deque([(root, 1)])  # (node, current_length)

        while queue:
            node, length = queue.popleft()
            max_length = max(max_length, length)

            if node.left:
                if node.left.val == node.val + 1:
                    queue.append((node.left, length + 1))
                else:
                    queue.append((node.left, 1))

            if node.right:
                if node.right.val == node.val + 1:
                    queue.append((node.right, length + 1))
                else:
                    queue.append((node.right, 1))

        return max_length

Complexity

  • ⏰ Time complexity: O(n), where (n) is the number of nodes in the tree. Each node is visited once in the BFS traversal.
  • 🧺 Space complexity: O(n), where (n) is the number of nodes in the tree. This accounts for the queue’s maximum size during traversal.

Method 2 - Using DFS

We can solve this problem using Depth-First Search (DFS). For each node, we check its left and right children to see if they continue the consecutive sequence. We will recursively calculate the length of the longest consecutive path for each subtree and keep track of the maximum length encountered.

Here are the steps we can take:

  1. Perform a DFS traversal of the tree.
  2. For each node, check if it can form a consecutive sequence with its left or right child.
  3. Update the current sequence length and the maximum sequence length found so far.
  4. Return the maximum length of the consecutive sequence path.

Code

Java
public class Solution {
    private int maxLength = 0;

    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, null, 0);
        return maxLength;
    }

    private void dfs(TreeNode node, TreeNode parent, int length) {
        if (node == null) {
            return;
        }

        if (parent != null && node.val == parent.val + 1) {
            length++;
        } else {
            length = 1;
        }

        maxLength = Math.max(maxLength, length);

        dfs(node.left, node, length);
        dfs(node.right, node, length);
    }
}
Python
class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        if not root:
            return 0

        self.max_length = 0

        def dfs(node, parent, length):
            if not node:
                return
            # Check if current node can continue the sequence
            if parent and node.val == parent.val + 1:
                length += 1
            else:
                length = 1

            self.max_length = max(self.max_length, length)

            # Recur for left and right children
            dfs(node.left, node, length)
            dfs(node.right, node, length)

        dfs(root, None, 0)
        return self.max_length

Complexity

  • ⏰ Time complexity: O(n), where (n) is the number of nodes in the tree. Each node is visited once in the DFS traversal.
  • 🧺 Space complexity: O(h), where (h) is the height of the tree. This accounts for the recursive call stack during DFS traversal.