549. Binary Tree Longest Consecutive Sequence II


Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note: All the values of tree nodes are in the range of [-1e7, 1e7].


Summary

Find the length of Longest Consecutive Path in Binary Tree. The path can be both increasing or decreasing i,e [1,2,3,4] and [4,3,2,1] are both considered valid. The path can be child-Parent-child not necessarily parent-child.

Solution

Approach #1 Brute Force [Time Limit Exceeded]

We can easily see that in a tree there is exactly one unique path one from one node to another. So, the number of paths possible will be equal to number of pairs of nodes , where is the number of nodes.

Brute force solution of this problem is to find the path between every two nodes and check whether it is increasing or decreasing. In this way we can find maximum length increasing or decreasing sequence.

Complexity Analysis

  • Time complexity : . Total possible number of paths are and checking every path whether it is increasing or decreasing will take for one path.

  • Space complexity : . paths each with nodes.

Approach #2 Single traversal [Accepted]

Algorithm

This solution is very simple. With every node, we associate two values/variables named and , where represents the length of the longest incrementing branch below the current node including itself, and represents the length of the longest decrementing branch below the current node including itself.

We make use of a recursive function longestPath(node) which returns an array of the form for the calling node. We start off by assigning both and as 1 for the current node. This is because the node itself always forms a consecutive increasing as well as decreasing path of length 1.

Then, we obtain the length of the longest path for the left child of the current node using longestPath[root.left]. Now, if the left child is just smaller than the current node, it forms a decreasing sequence with the current node. Thus, the value for the current node is stored as the left child's value + 1. But, if the left child is just larger than the current node, it forms an incrementing sequence with the current node. Thus, we update the current node's value as .

Then, we do the same process with the right child as well. But, for obtaining the and value for the current node, we need to consider the maximum value out of the two values obtained from the left and the right child for both and , since we need to consider the longest sequence possible.

Further, after we've obtained the final updated values of and for a node, we update the length of the longest consecutive path found so far as .

The following animation will make the process clear:

!?!../Documents/549_Binary_Tree_Longest_Sequence_ii.json:1000,563!?!

Complexity Analysis

  • Time complexity : . The whole tree is traversed only once.
  • Space complexity : . The recursion goes upto a depth of in the worst case.

Analysis written by: @vinod23

Submit Solution