Diagonal Sum of a Binary Tree
In this article, we will address the problem of calculating the diagonal sum of a binary tree. Diagonal sum involves summing up the values of nodes that belong to the same diagonal in a binary tree. We will explore how to implement this calculation in Java and print the sums of nodes in each diagonal.
Problem Statement
Given a binary tree, we want to calculate the diagonal sum of the tree. Diagonal sum means finding the sum of values of nodes that belong to the same diagonal, where the diagonals start from the topleft corner and move towards the bottomright corner of the tree.
Example
Let's consider a binary tree as an example:
10
/ \
/ \
2 4
/ / \
3 6 \
/ \ \
1 7 5
/ /
9 3
The diagonal sum of this tree is [19, 18, 13]
. Each value in the sum represents the sum of nodes in a
diagonal, starting from the topleft corner and moving towards the bottomright corner of the tree.
Idea to Solve the Problem
To calculate the diagonal sum of a binary tree, we can use a recursive approach. We will keep track of the diagonal distance of each node from the root and store the sum of nodes with the same diagonal distance in a HashMap. We start from the root with a diagonal distance of 0, and as we move to the left child, we increment the diagonal distance by 1. When we move to the right child, we keep the same diagonal distance. We update the diagonal sum in the HashMap as we encounter nodes.
Pseudocode
Here is the pseudocode for solving the problem:
function getDiagonalSum(node, distance, record):
if node is not null:
if distance in record:
record[distance] += node.data
else:
record[distance] = node.data
getDiagonalSum(node.left, distance + 1, record)
getDiagonalSum(node.right, distance, record)
function diagonalSum():
record = empty HashMap
getDiagonalSum(root, 0, record)
distance = 0
while distance in record:
print record[distance]
increment distance by 1
`
Algorithm Explanation
 Initialize an empty
HashMap
calledrecord
to store the diagonal sums.  Call the
getDiagonalSum
function starting from the root node with an initial distance of 0.  In the
getDiagonalSum
function: If the current node is not null, check if the current distance is already in
record
. If it is, add the node's data to the existing sum; otherwise, create a new entry for that distance.  Recursively call the function for the left child with an incremented distance (moving diagonally down to the left).
 Recursively call the function for the right child with the same distance (moving diagonally down to the right).
 If the current node is not null, check if the current distance is already in
 After the traversal is complete, iterate through the
record
map, starting from distance 0, and print the diagonal sums.  Increment the distance by 1 in each iteration until all diagonal sums are printed.
Code Solution

1) Diagonal sum of a binary tree in java
2) Diagonal sum of a binary tree in c++
3) Diagonal sum of a binary tree in golang
4) Diagonal sum of a binary tree in c#
5) Diagonal sum of a binary tree in php
6) Diagonal sum of a binary tree in node js
7) Diagonal sum of a binary tree in typescript
8) Diagonal sum of a binary tree in python
9) Diagonal sum of a binary tree in ruby
10) Diagonal sum of a binary tree in scala
11) Diagonal sum of a binary tree in swift
12) Diagonal sum of a binary tree in kotlin
13) Diagonal sum of a binary tree in vb.net
Time Complexity of the Code
The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the depthfirst traversal, and the HashMap operations take constant time.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment