Longest consecutive path in a Binary tree

Given a Binary tree, write code to find the length of longest path such that value of node in that path are consecutive and in decreasing order.

For example is the tree is

Then output should be: 3 because path (5, 4, 3) has all nodes in consecutively decreasing order.

Note that Path <5, 6, 7> are also consecutive, but they are not in decreasing order, hence not considered.

Solution:

Like most tree questions, this question can also be solved recursively. We need to see that in recursion what are the values that we need to make a decision at each node:

1. If value of a node is one less than value of its parent node, then this node will also contribute to the path that its parent node is part of. In this case we need, value of parent node and length of path till parent.
2. Otherwise a new path can start at the current node.

Each node will return the maximum path length found its point. And recursion will terminate when we hit the leaf nodes. Below is the code for same:  

struct Node
{
    int data;
    Node *left, *right;
    // Constructors
    Node():left(NULL), right(NULL){}
    Node(int v):data(v), left(NULL), right(NULL){}
};
// Recursive function to compute max consecutive path length
int maxConPathLengthRec(Node *root, int valueOfParent, int prevLengthOfPath)
{
    // Terminating Condition - 1.
    if (!root)
        return prevLengthOfPath;
    int newPathLen = prevLengthOfPath;
    if (root->data != valueOfParent - 1)
    {
        // Current node does not add to the length of path from parent.
        newPathLen = 0;
    }
    int x = maxConPathLengthRec(root->left, root->data, newPathLen + 1);
    int y = maxConPathLengthRec(root->right, root->data, newPathLen + 1);
    newPathLen = max(x, y);
    return  max(prevLengthOfPath, newPathLen);
}
// Wrapper function to be called by main function.
int maxConPathLength(Node *root)
{
    if(root == NULL)
        return 0;
    // Main function to compute the consecutive path length.
    // Passing root->data will force to restart at root.
    return maxConPathLengthRec(root, root->data, 0);
}
// Main Function.
int main()
{
    Node *root = new Node(5);
    root->left = new Node(6);
    root->right = new Node(4);
    root->left->left = new Node(7);
    root->left->right = new Node(1);
    root->right->left = new Node(3);
    root->right->right = new Node(9);
    cout<<"Max Cos. Decreasing path length :" << maxConPathLength(root)<<endl;
    return 0;
}