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
		map.Add(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.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. 
		Queue<Tree__nod> queue = new LinkedList<Tree__nod>();


			// 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. 
		queue.add(root);


		// 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;
					queue.add(curr.Lft);
				}
//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: