Count Diagonal Paths

Easy

0/40

Average time to solve is 20m

3 upvotes

Asked in companies

Problem statement

You are given a binary tree. Your task is to return the count of the diagonal paths to the leaf of the given binary tree such that all the values of the nodes on the diagonal are equal.

Note:

A diagonal traversal Consider lines of slope -1 passing between nodes.
         1
       /    \
     4        2
    /  \        \
   8    5         3
       /  \       /
      9    7      6

Example: Here potential diagonals are: 
1 -- 2 -- 3
4 -- 5 -- 7 -- 6
8 -- 9 -- 7

For Example

Input: 

     5
  /  \
 6      5
  \       \
   6       5

Output: 2 

Explanation: 

Diagonal 6 – 6 and 5 – 5 contains equal value. Therefore, the required output is 2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

The first line of input contains the elements of the tree in the level order form separated by a single space.
If any node does not have a left or right child, take -1 in its place. Refer to the example below.

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted below :

        1
       /    \
     4        2
    /  \        \
   8    5         3
       /   \     /
       9    7   6


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

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

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

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

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

Level 5 :
Left child of 9 = null (-1)
Right child of 9 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = 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).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

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

Output Format:

For every test case, return the count of the diagonal paths to the leaf of the given binary tree such that all the values of the nodes on the diagonal are equal.

Constraint :

1 <= T <= 100
1 <= N <= 3000
1 <= data <= 10^9

Where ‘T’ represents the number of test cases, ‘N’ is the number of nodes in the tree, and data denotes data contained in the node of a binary tree.

Time Limit: 1 sec

Sample Input 1:

2
5 6 5 -1 6 -1 5 -1 -1 -1 -1
5 6 5 -1 5 -1 5 -1 -1 -1 -1

Sample output 1:

2
1

Explanation to Sample Input 1

Test case 1:

  5
 /  \
 6   5
  \    \
   6     5


it is clear that the first diagonal path is 6 – 6 and the second is 5 – 5 contains an equal value. Therefore, the required output is 2.



Test case 2:

  5
 /    \
 6     5
  \       \
   5      5


it is clear that the first diagonal path is 6 -- 5, and the second is 5 -- 5.
Hence diagonal binary tree traversal when combined is 1 3 5 2 4

Sample Input 2:

1
1 -1 2 3 4 -1 -1 -1 -1

Sample output 2:

Note: Since there is only one such diagonal consisting of the only node 3, therefore, the count is 1

Hint 1

Try to sort the array based on the decreasing order of their frequency counts and increasing order of their index values.

Approaches (1)

Approach 1

Count diagonal paths from a node to a leaf consisting of the same valued nodes

The main idea here is to traverse the tree diagonally using a Map/Dictionary.

The algorithm will be-

Traverse the given binary tree in a diagonal order and store the starting node of each diagonal as the key and for each key, store all the values in that diagonal in a dictionary
To traverse the given binary tree in a diagonal order the main approach is to use a map/dictionary. We use different slope distances and use them as key in the map/dictionary. Value in the map/dictionary is a list (or dynamic array) of nodes. We traverse the tree to store values in the map/dictionary.
After the diagonal traversals, find the number of keys having the size of the set equal to 1.
Return the required count as the answer.

Time Complexity

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

We are iterating through the binary tree once and inserting nodes into the dictionary/map and the complexity grows as O(N).

Space Complexity

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

We are using an array/list to store every node value and the size ‘N’ dictionary/map to store node children. Hence overall space complexity will be O(N).

(100% EXP penalty)

Count Diagonal Paths

Console