Binary Tree Longest Consecutive Sequence Ii - Leetcode Solution

Problem Statement:

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

A consecutive path is a path where the values of consecutive nodes in the path differ by one. This path can be in either direction (left or right).

The length of a path is the number of nodes in that path.

Example 1:

Input: root = [1,2,3] Output: 2 Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input: root = [2,1,3] Output: 3 Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Approach:

For the given problem we can do a DFS approach. We take the root and traverse the tree and for each node we calculate the longest length of increasing and decreasing path starting from that node. We maintain a global variable max length which makes sure to have the highest value of path length found so far. For each node we update the maxLength if we found any path longer than current maxLength. Once we have the longest path length from left and right of the node, we can calculate the sum of both and see if it exceeds the maxLength then update it otherwise we leave it as it is.

Algorithm:

Function longestConsecutive(root: TreeNode) -> int:

1. Initialize maxLength to 0
2. Call dfs function on root with maxLength and return the result.

Function dfs(node: TreeNode, result: int) -> int:

1. If node is None, return 0
2. Let left and right be 0, call dfs for left child and right child, then.
3. If node has left and node value is one less than node.left.value then update left and store it in left variable.
4. If node has right and node value is one less than node.right.value then update right and store it in right variable.
5. Result <- max (result, 1+left+right)
6. Return max(left, right) + 1

Step 1: Check for base case, if node is None then return 0. Step 2: Initialize left and right by calling dfs for node.left and node.right respectively. Step 3 and 4: If the node has left or right child and value of left or right is one less than node value, then update left and right values. Step 5: Update result to have the maximum length of path found so far. Step 6: Return max value of left and right incremented by 1.

Complexity:

Time complexity: O(n), where n is the number of nodes in the tree. Because we are traversing the tree once.

Space complexity: O(h), where h is the height of the tree. Because at any time there are at most h frames in the stack due to recursion.

1