Longest ZigZag Path In Binary Tree

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
Twitter

Problem statement

You have been practicing on the topic binary tree for a few days. Your friend challenged you by giving you a binary tree and asked you to find the longest ZigZag path in the binary tree. ZigZag path of the binary tree is defined as below:

1. Choose any node in the binary tree and a direction to move further.
2. If the current direction is left, move to the right child of the current node, otherwise move to the left node.
3. Change the direction from right to left or from left to right.
4. Repeat the above steps until you are unable to move.
The longest path is defined as the number of nodes visited - 1.

Note :

1. Two nodes may have the same value associated with it.
2. The root node will be fixed and will be provided in the function.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer 'N', which denotes the number of nodes in the tree.

The second line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for 'NULL' node). Refer to the example for further clarification.
Example : 
Consider the binary tree


The input of the tree depicted in the image above will be like : 

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
Output Format : 
For each test case, print the longest ZigZag path in the binary tree.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5

It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 10^5.

Time Limit : 1 sec
Sample Input 1 :
2
5
1 2 3 4 5 -1 -1 -1 -1 -1 -1
3
2 3 1 -1 -1 -1 -1
Sample Output 1 :
2
1
Explanation For Sample Input 1 :
For the first test case, the tree will be :


The longest ZigZag path will be: 1 -> 2 -> 5

For the second test case, the tree will be :


The longest ZigZag path will be: 2 -> 1 or 2 -> 3
Sample Input 2 :
2
4
1 2 -1 -1 3 5 -1 -1 -1 -1
3
1 -1 3 -1 5 -1 -1
Sample Output 2 :
3
1
Hint

Think of storing the previous direction of each node and finding the maximum path iteratively. 

Approaches (2)
Breadth-First Search

The basic idea is to store the previous direction taken for each node. We use bfs to find the length of the longest ZigZag path. We use a queue to traverse the tree and an unordered map to store the previous direction and length of the longest path till the current node. We will represent the left direction with “-1”, whereas the right direction with ”1”.
 

Here is the algorithm :
 

  1. Create a variable (say, ‘ANS’) to store the longest path.
  2. Create an unordered map (say, ’MP’) that will store the direction and length of the path.
  3. Create a queue (say, ‘Q’) to traverse the tree.
  4. Check if the left child of ‘ROOT’ exists,
    • Push left child of ‘ROOT’ in ‘Q’.
    • Store the direction of the left child of ‘ROOT’ with “-1” and length 1.
  5. Similarly, check if the right child of ‘ROOT’ exists,
    • Push right child of ‘ROOT’ in ‘Q’.
    • Store the direction of the right child of ‘ROOT’ with “1” and length 1.
  6. Run a loop till ‘Q’ is not empty.
    • Create a variable (say, ‘CURR’) to store the ‘Q’’s current node.
    • Pop the element from ‘Q’.
    • Update ‘ANS’ by a maximum of ‘ANS’ and length till ‘CURR’ node.
    • Check if the previous direction taken was left.
      • Check if the right child of ‘CURR’ exists,
        • Push right child of ‘CURR’ in ‘Q’.
        • Store the direction of the right child of ‘ROOT’ with “1” and length 1 + length until the ‘CURR’ node.
      • Check if the left child of ‘CURR’ exists,
        • Push left child of ‘CURR’ in ‘Q’.
        • Store the direction of the left child of ‘ROOT’ with “-1” and length 1.
    • Similarly, check if the previous direction taken was right.
      • Check if the right child of ‘CURR’ exists,
        • Push right child of ‘CURR’ in ‘Q’.
        • Store the direction of the right child of ‘ROOT’ with “1” and length 1.
      • Check if the left child of ‘CURR’ exists,
        • Push left child of ‘CURR’ in ‘Q’.
        • Store the direction of the left child of ‘ROOT’ with “-1” and length 1 + length till the ‘CURR’ node.
  7. Finally, return ‘ANS’.
Time Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.

 

We traverse all the nodes of the binary tree once to find the longest path. Therefore, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.

 

We use a queue to store the nodes. We also use an unordered map to store the previous direction and the length till the current node. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Longest ZigZag Path In Binary Tree
Full screen
Console