Last Updated: 3 Dec, 2020
Diagonal Traversal of a binary tree.
Easy
Asked in companies
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
The diagonal traversal for the above tree is:
0 2 6 1 5 3 4 7
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:
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
Approaches
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:
- Assign the diagonal number of the root as 0.
- 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.
- Initialize an empty array to store the diagonal traversal, let’s say 'traversal'
- Iterate through the Map and add all the values of the Map to 'traversal'.
- Finally, Return 'traversal'.