Longest Consecutive Sequence in Binary Tree

Problem: Given a Binary Tree find the length of the longest path which comprises of nodes with consecutive values in increasing order. Every node is considered as a path of length 1.

Example:

Input:
   1
    \
     6
    / \
   2   7
        \
         8
Output:3
Explanation: Longest consecutive sequence path is 6-7-8.

Approach: Using Preorder traversal. Basically we will maintain two parameters in the recursive calls; one current sequence length say current_length and maximum sequence length say maximum_length. The names of the parameters itself tell what they are storing. 

Another parameter is expected_value which will tell what should be the value of current node's value in order to decide whether its consecutive sequence or not so if we find current node's value is expected_value then we will increment current_length otherwise current_length will be assigned back to 1 as this could be start of a new consecutive sequence. Off course if we find current_length is greater than maximum_length then current_length will be assigned to maximum_length.

For each recursive call we will assign expected_value to 1 + value of current node. In the end maximum_length will be our answer.

 

Implementation in C#:

        public int LongestConsecutiveSequence()

        {

            if (this.Root == null)

            {

                return 0;

            }

            int result = 0;

            this.LongestConsecutiveSequence(this.Root, this.Root.Value, 0, ref result);

            return result;

        }

        private void LongestConsecutiveSequence(BinaryTreeNode node, int expectedValue, int currLength, ref int maxLength)

        {

            if (node == null)

            {

                return;

            }

            currLength = node.Value == expectedValue ? currLength + 1 : 1;

            maxLength = Math.Max(currLength, maxLength);

            this.LongestConsecutiveSequence(node.LeftNode, node.Value + 1, currLength, ref maxLength);

            this.LongestConsecutiveSequence(node.RightNode, node.Value + 1, currLength, ref maxLength);

        }

Complexity: O(n)