Binary Tree Longest Consecutive Sequence II
Medium · Graphs · Explanation and code example
Single traversal
How it works
We can find the longest consecutive path in a single traversal by tracking two values at each node: the length of the longest increasing path going down and the length of the longest decreasing path going down. A node can potentially be the turning point where an increasing path from one subtree meets a decreasing path from the other, forming a complete consecutive sequence. By combining these two lengths at each node, we find the longest path passing through that node.
Steps
- Initialize a global variable to store the maximum path length.
- Define a DFS function that returns a pair:
[increasing length, decreasing length]starting from the current node. - If the current node is
null, return[0, 0]. - Start with increasing and decreasing lengths of
1(just the current node). - For the left child, if it exists and forms a consecutive sequence (value differs by
1), extend the appropriate length. - For the right child, do the same, taking the maximum with any length from the left.
- Update the global maximum with
(increasing + decreasing - 1), since the current node is counted twice. - Return
[increasing, decreasing]for the parent to use.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Where
nis the number of nodes in the input tree
Things to watch for
Mixing Up Increasing and Decreasing Directions
A node with value parent.val + 1 extends the increasing path from the child's perspective, but it is tracked as dcr (decreasing from root down). The naming can be confusing. Ensure you correctly match which direction each variable tracks.
Forgetting to Subtract 1 When Combining Paths
When combining increasing and decreasing paths through a node, that node is counted in both. The formula is inr + dcr - 1, not inr + dcr.
Only Considering One Child for Each Direction
Both left and right children can contribute to either increasing or decreasing paths. You must take the maximum from both children for each direction, not assume left contributes to one and right to the other.
Python code example
from typing import List
class Solution:
def longestConsecutive(self, root: TreeNode) -> int:
def longest_path(root: TreeNode) -> List[int]:
nonlocal maxval
if not root:
return [0, 0]
inr = dcr = 1
if root.left:
left = longest_path(root.left)
if (root.val == root.left.val + 1):
dcr = left[1] + 1
elif (root.val == root.left.val - 1):
inr = left[0] + 1
if root.right:
right = longest_path(root.right)
if (root.val == root.right.val + 1):
dcr = max(dcr, right[1] + 1)
elif (root.val == root.right.val - 1):
inr = max(inr, right[0] + 1)
maxval = max(maxval, dcr + inr - 1)
return [inr, dcr]
maxval = 0
longest_path(root)
return maxval
C++ code example
class Solution {
private:
int maxval = 0;
vector<int> longestPath(TreeNode* root) {
if (root == nullptr) {
return {0, 0};
}
int inr = 1, dcr = 1;
if (root->left != nullptr) {
vector<int> left = longestPath(root->left);
if (root->val == root->left->val + 1) {
dcr = left[1] + 1;
} else if (root->val == root->left->val - 1) {
inr = left[0] + 1;
}
}
if (root->right != nullptr) {
vector<int> right = longestPath(root->right);
if (root->val == root->right->val + 1) {
dcr = max(dcr, right[1] + 1);
} else if (root->val == root->right->val - 1) {
inr = max(inr, right[0] + 1);
}
}
maxval = max(maxval, dcr + inr - 1);
return {inr, dcr};
}
public:
int longestConsecutive(TreeNode* root) {
longestPath(root);
return maxval;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.