## 298. Binary Tree Longest Consecutive Sequence

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).

For example,

```   1
\
3
/ \
2   4
\
5
```
Longest consecutive sequence path is `3-4-5`, so return `3`.
```   2
\
3
/
2
/
1
```
Longest consecutive sequence path is `2-3`,not`3-2-1`, so return `2`.

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Top Down Depth-first Search) [Accepted]

\n

Algorithm

\n

A top down approach is similar to an in-order traversal. We use a variable `length` to store the current consecutive path length and pass it down the tree. As we traverse, we compare the current node with its parent node to determine if it is consecutive. If not, we reset the length.

\n
`private int maxLength = 0;\npublic int longestConsecutive(TreeNode root) {\n    dfs(root, null, 0);\n    return maxLength;\n}\n\nprivate void dfs(TreeNode p, TreeNode parent, int length) {\n    if (p == null) return;\n    length = (parent != null && p.val == parent.val + 1) ? length + 1 : 1;\n    maxLength = Math.max(maxLength, length);\n    dfs(p.left, p, length);\n    dfs(p.right, p, length);\n}\n`
\n

@lightmark presents a neat approach without storing the maxLength as a global variable.

\n
`public int longestConsecutive(TreeNode root) {\n    return dfs(root, null, 0);\n}\n\nprivate int dfs(TreeNode p, TreeNode parent, int length) {\n    if (p == null) return length;\n    length = (parent != null && p.val == parent.val + 1) ? length + 1 : 1;\n    return Math.max(length, Math.max(dfs(p.left, p, length),\n                                     dfs(p.right, p, length)));\n}\n`
\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nThe time complexity is the same as an in-order traversal of a binary tree with nodes.

\n
• \n
• \n

Space complexity : .\nThe extra space comes from implicit stack space due to recursion. For a skewed binary tree, the recursion could go up to levels deep.

\n
• \n
\n
\n

#### Approach #2 (Bottom Up Depth-first Search) [Accepted]

\n

Algorithm

\n

The bottom-up approach is similar to a post-order traversal. We return the consecutive path length starting at current node to its parent. Then its parent can examine if its node value can be included in this consecutive path.

\n
`private int maxLength = 0;\npublic int longestConsecutive(TreeNode root) {\n    dfs(root);\n    return maxLength;\n}\n\nprivate int dfs(TreeNode p) {\n    if (p == null) return 0;\n    int L = dfs(p.left) + 1;\n    int R = dfs(p.right) + 1;\n    if (p.left != null && p.val + 1 != p.left.val) {\n        L = 1;\n    }\n    if (p.right != null && p.val + 1 != p.right.val) {\n        R = 1;\n    }\n    int length = Math.max(L, R);\n    maxLength = Math.max(maxLength, length);\n    return length;\n}\n`
\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nThe time complexity is the same as a post-order traversal in a binary tree, which is .

\n
• \n
• \n

Space complexity : .\nThe extra space comes from implicit stack space due to recursion. For a skewed binary tree, the recursion could go up to levels deep.

\n
• \n
\n
'