
Asked in Amazon
Diagonal Traversal of a Binary Tree
Given a binary tree of integers, find its diagonal traversal. Refer to the example for clarification on diagonal traversal.
Example:
Explanation:
Consider lines at an angle of 135 degrees (with respect to the standard X-axis) in between nodes. All nodes between two consecutive lines belong to the same diagonal.
Output:
The diagonal traversal for the above tree is: 0 2 6 1 5 3 4 7
Input:
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. Values of nodes are separated by a single space. Use -1 in place of null nodes. -1 is not a tree node value.
Example:
The input for the tree depicted in the above 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
Output:
For each test case, return the diagonal traversal of the binary tree, separated by a single space.
Constraints:
- 1 <= T <= 100
- 0 <= N <= 3000
- 0 <= data <= 105 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
Note:
You don’t need to print anything, it has already been taken care of. Just implement the given function.

AnswerBot
4mo
Diagonal traversal of a binary tree involves printing nodes at the same diagonal in a specific order.
Traverse the tree in a diagonal manner, starting from the root node and moving towards the right ch...read more
Help your peers!
Add answer anonymously...
Top Software Developer Intern Interview Questions Asked at Amazon
Q. What is the code to calculate the distance between two nodes in a binary tree?
Q. For a given array, how would you count the number of inversions?
Q. Given a tree, find its diameter (the longest path between two nodes in the tree)...read more
Interview Questions Asked to Software Developer Intern at Other Companies
Top Skill-Based Questions for Amazon Software Developer Intern
Algorithms Interview Questions and Answers
250 Questions
Data Structures Interview Questions and Answers
250 Questions
Web Development Interview Questions and Answers
250 Questions
Operating Systems Interview Questions and Answers
250 Questions
System Design Interview Questions and Answers
250 Questions
C++ Interview Questions and Answers
150 Questions
Stay ahead in your career. Get AmbitionBox app


Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+
Reviews
10L+
Interviews
4 Cr+
Salaries
1.5 Cr+
Users
Contribute to help millions
AmbitionBox Awards
Get AmbitionBox app

