Posted on by Kalkicode
Code Binary Tree

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.

Diagonal Sum

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 top-left corner and move towards the bottom-right 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 top-left corner and moving towards the bottom-right 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

  1. Initialize an empty HashMap called record to store the diagonal sums.
  2. Call the getDiagonalSum function starting from the root node with an initial distance of 0.
  3. 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).
  4. After the traversal is complete, iterate through the record map, starting from distance 0, and print the diagonal sums.
  5. Increment the distance by 1 in each iteration until all diagonal sums are printed.

Code Solution

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 depth-first traversal, and the HashMap operations take constant time.

Comment

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