Diagonal Traversal of a binary tree.

Easy
0/40
Average time to solve is 10m
profile
Contributed by
8 upvotes
Asked in companies
AmazonSalesforceMicrosoft

Problem statement

You have been given a binary tree of integers. You are supposed to find the diagonal traversal(refer to Example) of the given binary tree.

Example:

Consider lines at an angle of 135 degrees(with respect to standard X- axis)  in between nodes. Then, all nodes between two consecutive lines belong to the same diagonal

alt text

The diagonal traversal for the above tree is: 

0 2 6 1 5 3 4 7
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. So -1 would not be a part of the tree nodes.
Example: 
The input for the tree depicted in the below image will be:

alt text

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)

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Note : 
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.

2.The input ends when all nodes at the last level are null(-1).
Output Format : 
For each test case, return the diagonal traversal of the binary tree separated by a single space.
Note : 
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100
0 <= N <= 3000
0 <= data <= 10^5 and data!=-1

Where ‘N’ is the total number of nodes in the binary tree, and 'data' is the value of the binary tree node

Time limit : 1 sec
Sample Input 1 :
2
1 2 3 4 -1 -1 -1 -1 -1
0 1 2 4 5 3 6 -1 -1 7 -1 -1 -1 -1 -1 -1 -1
Sample Output 1 :
1 3 2 4
0 2 6 1 5 3 4 7
Explanation of Sample Output 1 :
In test case 1,

alt text

Nodes 1 and 3 belong to diagonal number 0, node 2 belongs to diagonal 1, and node 4 belongs to diagonal number 2.

In test case 2, nodes 0,2,6 belong to diagonal 0, nodes 1,5,3 belong to diagonal 1, and nodes 4,7 belong to diagonal number 2.
Sample Input 2 :
2
1 -1 2 -1 -1
5 7 8 -1 -1 -1 -1
Sample Output 2 :
1 2
5 8 7
Explanation of Sample Output 2 :
In test case 1, nodes 1,2 both belong to diagonal number 0. 

In test case 2, nodes 5,8 belong to diagonal number 0, and node 7 belongs to diagonal number 1.
Hint

Can you think about using the root node as a reference to determine the diagonal number of that node?

Approaches (1)
Map based approach

The idea is to use the Map to store all the nodes of a particular diagonal number. We will use preorder traversal to update the Map. The key of the Map will be the diagonal number and the value of the Map will be an array/list that will store all nodes belonging to that diagonal. 

 

The steps are as follows:

 

  1. Assign the diagonal number of the root as 0.
  2. Do a preorder traversal of the binary tree and for each node keep track of the diagonal number.
    • Insert the value of the current node in the Map with the key as the diagonal number of the current node.
    • Now increase the diagonal number by 1 for the left child of the node and recursively traverse the left subtree.
    • Recursively traverse the right subtree and keep the diagonal number the same as the current node.
  3. Initialize an empty array to store the diagonal traversal, let’s say 'traversal'
  4. Iterate through the Map and add all the values of the Map to 'traversal'.
  5. Finally, Return 'traversal'.
Time Complexity

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

 

Since we are doing diagonal traversal which will visit each node of the given binary tree exactly once. Also, we are inserting ‘N’ values into the Map, and inserting each value takes (log N) time on average. Thus, the total time complexity will be O(N * log N).

Space Complexity

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

 

Since we are storing the value of all nodes in the Map which will take O(N) space. We are also storing all the values of the Map in an array/list, which will also take O(N) space. Thus, the total space complexity will be O(N).

Code Solution
(100% EXP penalty)
Diagonal Traversal of a binary tree.
Full screen
Console