Topics

# Diagonal Sum

Easy
0/40
Average time to solve is 23m
Contributed by

## Problem statement

Given a Binary Tree of 'N' nodes, find and print a list containing the sums of all the diagonals. When calculating the sum of each diagonal, consider the diagonals from right to left.

Diagonals of the binary tree are :

There are three diagonals :

Diagonal 1 : 8 10 14

Diagonal 2 : 3 6 7 13

Diagonal 3 : 1 4

Example :

For the given binary tree :

Output : 24 14 2

Explanation: Rightmost diagonal contains elements {5, 10 , 9} its sum is 24, middle diagonal contains elements {6, 3, 5} its sum is 14, leftmost diagonal contains elements {2}. Thus the answer should be “24 14 2”.
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
0 <= N <= 10^5
0 <= node.data <= 10^9

Time Limit : 1 sec
Sample Input 1 :
1 2 3 -1 4 4 -1 -1 5 6 -1 -1 -1 -1 -1
Sample Output 1:
4 15 6
Explanation For Sample Input 1 :
The input binary tree will be represented as

From the above representation, the rightmost diagonal contains elements {1, 3}, the middle diagonal contains elements {2, 4, 4, 5} and leftmost diagonal elements are {6}. Thus the list should contain “4 15 6”.
Sample Input 2:
1 2 3 -1 -1 -1 -1
Sample Output 2 :
4 2
Console