# Finding Diagonal Sum in a Binary Tree

## Implementation

``````// Writing the C++ program to see the implementation and determine the diagonal sum of a binary tree.
#include <bits/stdc++.h>
using namespace std;

struct __nod
{
int record;
struct __nod* Lft;
struct __nod* Rt;
};

struct __nod* new__nod(int record)
{
struct __nod* __nod =
(struct __nod*)malloc(sizeof(struct __nod));

__nod->record = record;
__nod->Lft = __nod->Rt = NILL;

return __nod;
}

// we will now describe some terminologies here,
Root- it’s the base of the binary tree
// vd – it’s the vertical distance of the diagonal
// diagSum – it’s the map to store diagonal
// Sum( its passed by the reference)
void diagSumUtil(struct __nod* root,
int vd, map<int, int> &diagSum)
{
if(!root)
return;

diagSum[vd] += root->record;

// incrementing the vertical distance(vd) of the left child.
diagSumUtil(root->Lft, vd + 1, diagSum);

// the vertical distance on the right child remains unchanged.
diagSumUtil(root->Rt, vd, diagSum);
}

// creating a new function will help us evaluate the diagonal sum of the given binary tree.
void diagSum(struct __nod* root)
{

// creating a map that will store all the diagonal sum
map<int, int> diagSum;

diagSumUtil(root, 0, diagSum);

map<int, int>::iterator it;
cout << "Diagonal sum in a binary tree is - ";

for(it = diagSum.begin();
it != diagSum.end(); ++it)
{
cout << it->second << " ";
}
}

// writing the main code to test the above functions
int main()
{
struct __nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(9);
root->Lft->Rt = new__nod(6);
root->Rt->Lft = new__nod(4);
root->Rt->Rt = new__nod(5);
root->Rt->Lft->Rt = new__nod(7);
root->Rt->Lft->Lft = new__nod(12);
root->Lft->Rt->Lft = new__nod(11);
root->Lft->Lft->Rt = new__nod(10);

diagSum(root);

return 0;
}
``````

Output: Example 2

``````// Writing the C# program to see the implementation and determine the diagonal sum of a binary tree.
using System;
using System.Collections.Generic;

// creating a new tree node
public

class Tree__nod
{
public
int record; // the node has all the record, i.e., data
public

int vd; // it’s the vertical distance measured diagonally
public
Tree__nod Lft, Rt; // it's the left and right child reference.

// creating a constructor for the tree node.
public Tree__nod(int record)
{
this.record = record;
vd = int.MaxValue;
Lft = Rt = NILL;
}
}

// creating a class for the tree and naming it the same.
public class Tree
{
Tree__nod root;//T ree root

// Constructor for the tree
public Tree(Tree__nod root)
{
this.root = root;
}

// creating the diagonal sum method
public void diagSum()
{

// creating a queue that will store all the tree nodes.
Queue<Tree__nod> queue = new Queue<Tree__nod>();

// creating a map that will store the sum of all the nodes lying diagonally.
Dictionary<int, int> map = new Dictionary<int,int>();

// we have to allot the vertical distance of the root as 0.
root.vd = 0;

// we have to add the root node to the queue.
queue.Enqueue(root);

// creating a loop while the queue is not empty.
while (queue.Count != 0)
{

// we have to remove the front tree node from the queue
Tree__nod curr = queue.Dequeue();

// From the dequeued node, we must get the vertical distance.
int vd = curr.vd;

// we have to get the sum of the node's right child and the right of the right child.
while (curr != NILL)
{
int prevSum;
if(!map.ContainsKey(vd))
prevSum = 0;
else
prevSum = map[vd];

if(map.ContainsKey(vd))
map[vd] = prevSum + curr.record;
else

// if, in the case of any of the nodes given below, the left child is not NILL, then we have to add it to the queue to process in the future.
if (curr.Lft != NILL)
{
curr.Lft.vd = vd + 1;
queue.Enqueue(curr.Lft);
}

//We can move to the current node at the right child.
curr = curr.Rt;
}
}

// we have to explore the elements using an iterator.
Console.Write("Diagonal sum in a binary tree is - ");
foreach(KeyValuePair<int, int> iterator in map)
{

// Map.Entry<int, int> me = iterator.next();
Console.Write(iterator.Value + " ");
}
}
}

// writing the main code to test the above functions
public class DiagSum
{
public static void Main(String[] args)
{
Tree__nod root = new Tree__nod(1);
root.Lft = new Tree__nod(2);
root.Rt = new Tree__nod(3);
root.Lft.Lft = new Tree__nod(9);
root.Lft.Rt = new Tree__nod(6);
root.Rt.Lft = new Tree__nod(4);
root.Rt.Rt = new Tree__nod(5);
root.Rt.Lft.Lft = new Tree__nod(12);
root.Rt.Lft.Rt = new Tree__nod(7);
root.Lft.Rt.Lft = new Tree__nod(11);
root.Lft.Lft.Rt = new Tree__nod(10);
Tree tree = new Tree(root);
tree.diagSum();
}
}
``````

Output: Example 3

``````// Writing the Java program to see the implementation and determine the diagonal sum of a binary tree.
import java.util.*;
import java.util.Map.Entry;
// creating a new tree nod
class Tree__nod
{
int record; // the node has all the record, i.e., data
int vd; // it’s the vertical distance measured diagonally
Tree__nod Lft, Rt; // it’s the left and right child reference

// creating a constructor for the tree node.
public Tree__nod(int record)
{
this.record = record;
vd = Integer.MAX_VALUE;
Lft = Rt = NILL;
}
}

// creating a class for the tree and naming it the same.
class Tree
{
Tree__nod root;//Tree root
// Constructor for the tree

public Tree(Tree__nod root) { this.root = root; }

// creating the diagonal sum method
public void diagSum()
{
// creating a queue that will store all the tree nodes.

// creating a map that will store the sum of all the nodes lying diagonally.
Map<Integer, Integer> map = new TreeMap<>();

// we have to allot the vertical distance of the root as 0.
root.vd = 0;

// we have to add the root node to the queue.

// creating a loop while the queue is not empty.
while (!queue.isEmpty())
{
// we have to remove the front tree node from the queue
Tree__nod curr = queue.remove();

// From the dequeued node, we must get the vertical distance.
int vd = curr.vd;

// we have to get the sum of the node's right child and the right of the right child.

while (curr != NILL)
{
int prevSum = (map.get(vd) == NILL)? 0: map.get(vd);
map.put(vd, prevSum + curr.record);
// if, in the case of any of the nodes given below, the left child is not NILL, then we have to add it to the queue to process in the future.
if (curr.Lft != NILL)
{
curr.Lft.vd = vd+1;
}
//We can move to the current node at the right child.
curr = curr.Rt;
}
}

// Make an entry set from the map.
Set<Entry<Integer, Integer>> set = map.entrySet();

// we have to explore the elements using an iterator.
Iterator<Entry<Integer, Integer>> iterator = set.iterator();

// we have to explore the elements using an iterator.
System.out.print("Diagonal sum in a binary tree is - ");
while (iterator.hasNext())
{
Map.Entry<Integer, Integer> me = iterator.next();

System.out.print(me.getValue()+" ");
}
}
}

// writing the main code to test the above functions
public class DiagSum
{
public static void main(String[] args)
{
Tree__nod root = new Tree__nod(1);
root.Lft = new Tree__nod(2);
root.Rt = new Tree__nod(3);
root.Lft.Lft = new Tree__nod(9);
root.Lft.Rt = new Tree__nod(6);
root.Rt.Lft = new Tree__nod(4);
root.Rt.Rt = new Tree__nod(5);
root.Rt.Lft.Lft = new Tree__nod(12);
root.Rt.Lft.Rt = new Tree__nod(7);
root.Lft.Rt.Lft = new Tree__nod(11);
root.Lft.Lft.Rt = new Tree__nod(10);
Tree tree = new Tree(root);
tree.diagSum();
}
}
``````

Output: Example 4

``````<script>
// Writing the Javascript program to see the implementation and determine the diagonal sum of a binary tree.
class Tree__nod {
// creating a new tree node
// creating a constructor for the tree node.
constructor(record) {
this.record = record; // the node has all the record,i.e data
this.vd = 2147483647; // it’s the vertical distance measured diagonally
this.Lft = NILL; // it’s the left and right child reference
this.Rt = NILL;
}
}
// creating a class for the tree and naming it the same.
class Tree {
// Constructor for the tree
constructor(root) {
this.root = root; //Tree root
}

// creating the diagonal sum method
diagSum() {
// creating a queue that will store all the tree nodes.

var queue = [];

// creating a map that will store the sum of all the nodes lying diagonally.
var map = {};

// we have to allot the vertical distance of the root as 0.
this.root.vd = 0;

// we have to add the root node to the queue.
queue.push(this.root);

// creating a loop while the queue is not empty.
while (queue. length != 0) {
// we have to remove the front tree node from the queue
var curr = queue.shift();

// From the dequeued node, we must get the vertical distance.
var vd = curr.vd;

// we have to get the sum of the node's right child and the right of the right child.
while (curr != NILL) {
var prevSum;
if (!map.hasOwnProperty(vd))
prevSum = 0;
else prevSum = map[vd];

if (map.hasOwnProperty(vd))
map[vd] = prevSum + curr.record;
else
map[vd] = prevSum + curr.record;

// if, in the case of any of the nodes given below, the left child is not NILL, then we have to add it to the queue to process in the future.
if (curr.Lft != NILL) {
curr.Lft.vd = vd + 1;
queue.push(curr.Lft);
}

//We can move to the current node at the right child.
curr = curr.Rt;
}
}

// we have to explore the elements using an iterator.
document.write("Diagonal sum in a binary tree is - ");
for (const [key, value] of Object.entries(map)) {
// Map.Entry<int, int> me = iterator.next();
document.write(value + " ");
}
}
}
// writing the main code to test the above functions

var root = new Tree__nod(1);
root.Lft = new Tree__nod(2);
root.Rt = new Tree__nod(3);
root.Lft.Lft = new Tree__nod(9);
root.Lft.Rt = new Tree__nod(6);
root.Rt.Lft = new Tree__nod(4);
root.Rt.Rt = new Tree__nod(5);
root.Rt.Lft.Lft = new Tree__nod(12);
root.Rt.Lft.Rt = new Tree__nod(7);
root.Lft.Rt.Lft = new Tree__nod(11);
root.Lft.Lft.Rt = new Tree__nod(10);
var tree = new Tree(root);
tree.diagSum();

</script>
``````

Output: Example 5

``````# Write a new program to determine the binary tree's diagonal sum.

class new__nod:
def __init__(self, record):
self.record = record
self.Lft = self.Rt = None

# Write a function to evaluate the height of the binary tree.
# We will now describe some terminologies here,
Root- it’s the base of the binary tree
# vd – it’s the vertical distance of the diagonal
# diagSum – it’s the map to store diagonal
# Sum( its passed by the reference)
def diagSumUtil(root, vd, diagSum) :

if(not root):
return

if vd not in diagSum:
diagSum[vd] = 0
diagSum[vd] += root.record

# Incrementing the vertical distance(vd) of the left child.
diagSumUtil(root.Lft, vd + 1,
diagSum)

# The vertical distance on the right child remains unchanged.
diagSumUtil(root.Rt, vd,
diagSum)

# Creating a new function that will help us evaluate the diagonal sum of the given binary tree.
def diagSum(root) :

# Creating a map that will store all the diagonal sum
diagSum = dict()

diagSumUtil(root, 0, diagSum)

print("Diagonal sum in a binary tree is - ",
end = "")

For it in diagSum:
print(diagSum[it], end = " ")

# Writing the main code to test the above functions
if __name__ == '__main__':
root = new__nod(1)
root.Lft = new__nod(2)
root.Rt = new__nod(3)
root.Lft.Lft = new__nod(9)
root.Lft.Rt = new__nod(6)
root.Rt.Lft = new__nod(4)
root.Rt.Rt = new__nod(5)
root.Rt.Lft.Rt = new__nod(7)
root.Rt.Lft.Lft = new__nod(12)
root.Lft.Rt.Lft = new__nod(11)
root.Lft.Lft.Rt = new__nod(10)

diagSum(root)
``````

Output: 