# Idea similar to finding paths that sum up to a given value.

• We need to consider 6 cases.

1. Root + left subtree forms an increasing sequence if root + 1 == node.left.
2. Root + left subtree forms a decreasing sequence if root -1 == node.left.
3 & 4 are similar cases for the right subtree.
3. if the root + 1 == node.left and root -1 == node.right, we need to club the increasing sequence from left sub-tree and the decreasing sequence from right sub-tree to form an increasing V-path.
4. if the root - 1 == node.left and root + 1 == node.right, we need to club the decreasing sequence from left sub-tree and the increasing sequence from right sub-tree to form a decreasing V path.

The longest increasing and decreasing subtree starting at root need to be returned.

``````public class Solution {
private int maxPath = 0;
public int LongestConsecutive(TreeNode root)
{
GetLongestConsecutive(root);
return maxPath;
}

public int[] GetLongestConsecutive(TreeNode root)
{
if (root == null)
{
return null;
}

int[] curSequence = new int[] { 1, 1 }, rightSequences = null, leftSequences = null;

if (root.left != null)
{
leftSequences = GetLongestConsecutive(root.left);
if (root.val + 1 == root.left.val)
{
// Increasing sequence
curSequence[0] = leftSequences[0] + 1;
}

if (root.val - 1 == root.left.val)
{
// Decreasing sequence
curSequence[1] = leftSequences[1] + 1;
}
}

if (root.right != null)
{
rightSequences = GetLongestConsecutive(root.right);
if (root.val + 1 == root.right.val)
{
// Increasing sequence
curSequence[0] = Math.Max(curSequence[0], rightSequences[0] + 1);
}

if (root.val - 1 == root.right.val)
{
// Decreasing sequence
curSequence[1] = Math.Max(curSequence[1], rightSequences[1] + 1);
}
}

maxPath = Math.Max(maxPath, Math.Max(curSequence[0], curSequence[1]));
if (root.left != null && root.right != null)
{
if (root.left.val - 1 == root.val && root.val == root.right.val + 1)
{
// Increasing v sequence.
maxPath = Math.Max(maxPath, leftSequences[0] + rightSequences[1] + 1);
}

if (root.left.val + 1 == root.val && root.val == root.right.val - 1)
{
// Decreasing v sequence.
maxPath = Math.Max(maxPath, leftSequences[1] + rightSequences[0] + 1);
}
}

return curSequence;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.