LeetFree - Leaked Interview questions from Google Facebook Amazon Microsoft LinkedIn

Question
Solution

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
Solution
- Approach #1 Brute Force [Time Limit Exceeded]
- Approach #2 Single traversal [Accepted]
\n

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 ${{N}\\choose{2}}$ , where $N$ 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

\n
Time complexity : $O(n^3)$ . Total possible number of paths are $n^2$ and checking every path whether it is increasing or decreasing will take $O(n)$ for one path.
\n
\n
Space complexity : $O(n^3)$ . $n^2$ paths each with $O(n)$ nodes.
\n

Approach #2 Single traversal [Accepted]

Algorithm

This solution is very simple. With every node, we associate two values/variables named $inr$ and $dcr$ , where $incr$ represents the length of the longest incrementing branch below the current node including itself, and $dcr$ 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 $[inr, dcr]$ for the calling node. We start off by assigning both $inr$ and $dcr$ 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 $dcr$ value for the current node is stored as the left child\'s $dcr$ 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 $inr$ value as $left\\_child(inr) + 1$ .

Then, we do the same process with the right child as well. But, for obtaining the $inr$ and $dcr$ 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 $inr$ and $dcr$ , since we need to consider the longest sequence possible.

Further, after we\'ve obtained the final updated values of $inr$ and $dcr$ for a node, we update the length of the longest consecutive path found so far as $maxval = \\text{max}(inr + dcr - 1)$ .

The following animation will make the process clear:

\n\n

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