# Diagonal Sum of a Binary Tree

Here given code implementation process.

``````/*
C Program
+ Diagonal Sum of a Binary Tree
*/
#include <stdio.h>
#include <stdlib.h>
//Structure of Binary Tree node
struct Node
{
int data;
struct Node*left,*right;
};

struct List
{
int order,data;
struct List*next;

};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes

struct Node* insert(int data)
{
//create dynamic memory to new binary tree node
struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));
if(new_node!=NULL)
{
//set data and pointer values
new_node->data=data;
new_node->left=NULL; //Initially node left-pointer is NULL
new_node->right=NULL;//Initially node right-pointer is NULL
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;

}
struct List* create(int order,int data)
{
struct List*new_node=(struct List*)malloc(sizeof(struct List));
if(new_node!=NULL)
{
new_node->next=NULL;
new_node->data=data;
new_node->order=order;
return new_node;
}else
{
printf("Memory Overflow\n");
exit(0);

}
}
//Adding a new element in sorted order when get new left bottom element
{
struct List*new_node=NULL,*back=NULL;
if(*result!=NULL)
{

struct List*temp=*result;

if(temp->order > order)
{
//New Diagonal element
new_node=create(order,data);
new_node->next=*result;
*result=new_node;
}else{
int status=1;
//Check inserted node are exist or not
while(temp!=NULL)
{

if(temp->order==order)
{
temp->data+=data;

status=0;
break;
}
temp=temp->next;
}

if(status==1)
{
temp=*result;

while(temp!=NULL)
{
back=temp;
if(temp->order > order)
{
break;
}else
{
temp=temp->next;
}
}
new_node=create(order,data);
new_node->next=back->next;
back->next=new_node;
}
}
}else{
//When first node are get
*result=create(order,data);
}

}
void removeList(struct List**bucket)
{
struct List*temp=NULL;
while(*bucket)
{
temp=*bucket;
*bucket=temp->next;
free(temp);
temp=NULL;
}
}

void get_diagonal(struct Node*node,struct List**bucket,int order)
{

if(node!=NULL)
{
get_diagonal(node->left,bucket,order+1);
get_diagonal(node->right,bucket,order);
}
}
void print_diagonal(struct Node*root)
{
struct List*bucket=NULL;

//Get the Sum of diagonal elements
get_diagonal(root,&bucket,0);

struct List*temp=bucket;
//Show Sum of diagonal elements
while(temp!=NULL)
{
printf("%3d",temp->data );
temp=temp->next;
}
//Removing all List element
removeList(&bucket);
}
int main(){

struct Node*root=NULL;

/*  Make A Binary Tree
-----------------------
10
/   \
2     4
/    /  \
3    6    \
/ \    \
1   7    5
/    /
9    3

*/

//Insertion of binary tree nodes
root               = insert(10);
root->left         = insert(2);
root->left->left   = insert(3);

root->right        = insert(4);
root->right->right = insert(5);
root->right->left  = insert(6);
root->right->left->left  = insert(1);

root->right->right->left = insert(3);

root->right->left->right  = insert(7);
root->right->left->right->left = insert(9);

print_diagonal(root);

return 0;
}
```
```

#### Output

``19 18 13``
``````/*
C++ Program
Diagonal Sum of a Binary Tree
*/
#include<iostream>

using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int value) {
this->data = value;
this->left = this->right = NULL;
}
};
class MyList {
public:
int order, data;
MyList *next;
MyList(int level, int value) {
this->order = level;
this->data = value;
this->next = NULL;
}
};
class BinaryTree {
public:
Node *root;
MyList *bucket;
BinaryTree() {
this->root = NULL;
this->bucket = NULL;
}
void addList(int level, int value) {
MyList *temp = this->bucket;
int status = 1;
while (temp != NULL) {
if (temp->order == level) {
status = 0;
temp->data += value;
break;;
}
temp = temp->next;
}
if (status == 0) {
return;
}
MyList *new_node = NULL, *per = NULL;
new_node = new MyList(level, value);
if (this->bucket != NULL) {
temp = this->bucket;
if (temp->order > level) {
new_node->next = this->bucket;
this->bucket = new_node;
} else {
while (temp != NULL && temp->order < level) {
per = temp;
temp = temp->next;
}
new_node->next = per->next;
per->next = new_node;
}
} else {
this->bucket = new_node;
}
}
void removeList() {
MyList *temp = NULL;
while (this->bucket != NULL) {
temp = this->bucket;
this->bucket = temp->next;
temp = NULL;
}
}
void get_diagonal(Node *head, int level) {
}
}
void diagonal_sum() {
MyList *temp = this->bucket;
while (temp != NULL) {
cout << "  "<< temp->data;
temp = temp->next;
}
}
};
int main() {
BinaryTree obj;
/* Make A Binary Tree
-----------------------
10
/   \
2     4
/    /  \
3    6    \
/ \    \
1   7    5
/    /
9    3

*/
obj.root = new Node(10);
obj.root->left = new Node(2);
obj.root->left->left = new Node(3);
obj.root->right = new Node(4);
obj.root->right->right = new Node(5);
obj.root->right->left = new Node(6);
obj.root->right->left->left = new Node(1);
obj.root->right->right->left = new Node(3);
obj.root->right->left->right = new Node(7);
obj.root->right->left->right->left = new Node(9);
obj.get_diagonal(obj.root, 0);
obj.diagonal_sum();
obj.removeList();
return 0;
}```
```

#### Output

``19 18 13``
``````/*
Java Program
Diagonal Sum of a Binary Tree
*/

//Class of Binary Tree node
class Node {

public int data;
public Node left, right;
//Make a tree node
public Node(int value) {
//Assign field values
data = value;
left = right = null;
}
}

class MyList {
public int order, data;
public MyList next;
public MyList(int level, int value) {
order = level;
data = value;
next = null;
}
}
public class BinaryTree {

public Node root;
public MyList bucket;

public BinaryTree() {
//Set initial initial values
root = null;
bucket = null;
}
//When vertical nodes are already exist in same then
//updating its value to add new data
public void addList(int level, int value) {

MyList temp = this.bucket;
int status = 1;
//Check vertical node alrady exist or not
while (temp != null) {
if (temp.order == level) {
status = 0;
//when vertical order exist
temp.data += value; //add vertical node data
break;
}
temp = temp.next;
}
if (status == 0) {
return;
}

MyList new_node = null, per = null;

new_node = new MyList(level, value);

if (this.bucket != null) {
temp = this.bucket;
if (temp.order > level) {
//smallest element
new_node.next = this.bucket;
this.bucket = new_node;
} else {

while (temp != null && temp.order < level) {
per = temp;
temp = temp.next;
}
new_node.next = per.next;
per.next = new_node;

}

} else {
//When first element of list
this.bucket = new_node;
}
}
public void removeList() {
MyList temp = null;
while (this.bucket != null) {
temp = bucket;
this.bucket = temp.next;
temp = null;
}
}

public void get_diagonal(Node head, int order) {

}
}
public void diagonal_sum() {
MyList temp = this.bucket;

while (temp != null) {
System.out.print("  " + temp.data);
temp = temp.next;
}

}

public static void main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();

/* Make A Binary Tree
-----------------------
10
/   \
2     4
/    /  \
3    6    \
/ \    \
1   7    5
/    /
9    3

*/

//binary tree nodes
obj.root = new Node(10);
obj.root.left = new Node(2);
obj.root.left.left = new Node(3);
obj.root.right = new Node(4);
obj.root.right.right = new Node(5);
obj.root.right.left = new Node(6);
obj.root.right.left.left = new Node(1);
obj.root.right.right.left = new Node(3);
obj.root.right.left.right = new Node(7);
obj.root.right.left.right.left = new Node(9);
obj.get_diagonal(obj.root, 0);
obj.diagonal_sum();
obj.removeList();
}
}```
```

#### Output

``19 18 13``
``````/*
C# Program
Diagonal Sum of a Binary Tree
*/
using System;
//Class of Binary Tree node
public class Node {

public int data;
public Node left, right;
//Make a tree node
public Node(int value) {
//Assign field values
data = value;
left = right = null;
}
}

public class MyList {
public int order, data;
public MyList next;
public MyList(int level, int value) {
order = level;
data = value;
next = null;
}
}
public class BinaryTree {

public Node root;
public MyList bucket;

public BinaryTree() {
//Set initial initial values
root = null;
bucket = null;
}
//When vertical nodes are already exist in same then
//updating its value to add new data
public void addList(int level, int value) {

MyList temp = this.bucket;
int status = 1;
//Check vertical node alrady exist or not
while (temp != null) {
if (temp.order == level) {
status = 0;
//when vertical order exist
temp.data += value; //add vertical node data
break;
}
temp = temp.next;
}
if (status == 0) {
return;
}

MyList new_node = null, per = null;

new_node = new MyList(level, value);

if (this.bucket != null) {
temp = this.bucket;
if (temp.order > level) {
//smallest element
new_node.next = this.bucket;
this.bucket = new_node;
} else {

while (temp != null && temp.order < level) {
per = temp;
temp = temp.next;
}
new_node.next = per.next;
per.next = new_node;

}

} else {
//When first element of list
this.bucket = new_node;
}
}
public void removeList() {
MyList temp = null;
while (this.bucket != null) {
temp = bucket;
this.bucket = temp.next;
temp = null;
}
}

public void get_diagonal(Node head, int order) {

}
}
public void diagonal_sum() {
MyList temp = this.bucket;

while (temp != null) {
Console.Write("  " + temp.data);
temp = temp.next;
}

}

public static void Main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();

/* Make A Binary Tree
-----------------------
10
/   \
2     4
/    /  \
3    6    \
/ \    \
1   7    5
/    /
9    3

*/

//binary tree nodes
obj.root = new Node(10);
obj.root.left = new Node(2);
obj.root.left.left = new Node(3);
obj.root.right = new Node(4);
obj.root.right.right = new Node(5);
obj.root.right.left = new Node(6);
obj.root.right.left.left = new Node(1);
obj.root.right.right.left = new Node(3);
obj.root.right.left.right = new Node(7);
obj.root.right.left.right.left = new Node(9);
obj.get_diagonal(obj.root, 0);
obj.diagonal_sum();
obj.removeList();
}
}```
```

#### Output

``19 18 13``
``````# Python Program
# Diagonal Sum of a Binary Tree

class Node :

def __init__(self, value) :
self.data = value;
self.left = self.right = None;

class MyList :

def __init__(self, level, value) :
self.order = level;
self.data = value;
self.next = None;

class BinaryTree :

def __init__(self) :
self.root = None;
self.bucket = None;

temp = self.bucket;
status = 1;
while (temp != None) :
if (temp.order == level) :
status = 0;
temp.data += value;
break;

temp = temp.next;

if (status == 0) :
return;

new_node = None;
per = None;
new_node = MyList(level, value);
if (self.bucket != None) :
temp = self.bucket;
if (temp.order > level) :
new_node.next = self.bucket;
self.bucket = new_node;
else :
while (temp != None and temp.order < level) :
per = temp;
temp = temp.next;

new_node.next = per.next;
per.next = new_node;

else :
self.bucket = new_node;

def removeList(self) :
temp = None;
while (self.bucket != None) :
temp = self.bucket;
self.bucket = temp.next;
temp = None;

def diagonal_sum(self) :
temp = self.bucket;
while (temp != None) :
print(temp.data,end="  ");
temp = temp.next;

def main() :
obj = BinaryTree();
# Make A Binary Tree
#
#           10
#         /   \
#        2     4
#       /    /  \
#      3    6    \
#          / \    \
#         1   7    5
#            /    /
#           9    3
#
obj.root = Node(10);
obj.root.left = Node(2);
obj.root.left.left = Node(3);
obj.root.right = Node(4);
obj.root.right.right = Node(5);
obj.root.right.left = Node(6);
obj.root.right.left.left = Node(1);
obj.root.right.right.left = Node(3);
obj.root.right.left.right = Node(7);
obj.root.right.left.right.left = Node(9);
obj.get_diagonal(obj.root, 0);
obj.diagonal_sum();
obj.removeList();

if __name__ == "__main__":
main()```
```

#### Output

``19 18 13``
``````# Ruby Program
# Diagonal Sum of a Binary Tree
class Node
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = @right = nil
end
end

class MyList
attr_accessor :order, :data, :next
def initialize(level, value)
@order = level
@data = value
@next = nil
end
end

class BinaryTree
attr_accessor :root, :bucket
def initialize()
@root = nil
@bucket = nil
end
temp = self.bucket
status = 1
while (temp != nil)
if (temp.order == level)
status = 0
temp.data += value
break
end
temp = temp.next
end
if (status == 0)
return
end
new_node = nil
per = nil
new_node = MyList.new(level, value)
if (self.bucket != nil)
temp = self.bucket
if (temp.order > level)
new_node.next = self.bucket
self.bucket = new_node
else
while (temp != nil and temp.order < level)
per = temp
temp = temp.next
end
new_node.next = per.next
per.next = new_node
end
else
self.bucket = new_node
end
end
def removeList()
temp = nil
while (self.bucket != nil)
temp = @bucket
self.bucket = temp.next
temp = nil
end
end
end
end
def diagonal_sum()
temp = self.bucket
while (temp != nil)
print("  ", temp.data)
temp = temp.next
end
end
end

def main()
obj = BinaryTree.new()
# Make A Binary Tree
#
#           10
#         /   \
#        2     4
#       /    /  \
#      3    6    \
#          / \    \
#         1   7    5
#            /    /
#           9    3
#
obj.root = Node.new(10)
obj.root.left = Node.new(2)
obj.root.left.left = Node.new(3)
obj.root.right = Node.new(4)
obj.root.right.right = Node.new(5)
obj.root.right.left = Node.new(6)
obj.root.right.left.left = Node.new(1)
obj.root.right.right.left = Node.new(3)
obj.root.right.left.right = Node.new(7)
obj.root.right.left.right.left = Node.new(9)
obj.get_diagonal(obj.root, 0)
obj.diagonal_sum()
obj.removeList()
end
main()```
```

#### Output

``19 18 13``
``````<?php
/*
Php Program
Diagonal Sum of a Binary Tree
*/
class Node {
public \$data;
public \$left;
public \$right;

function __construct(\$value) {
\$this->data = \$value;
\$this->left = \$this->right = null;
}
}
class MyList {
public \$order;
public \$data;
public \$next;

function __construct(\$level, \$value) {
\$this->order = \$level;
\$this->data = \$value;
\$this->next = null;
}
}
class BinaryTree {
public \$root;
public \$bucket;

function __construct() {
\$this->root = null;
\$this->bucket = null;
}
public
\$temp = \$this->bucket;
\$status = 1;
while (\$temp != null) {
if (\$temp->order == \$level) {
\$status = 0;
\$temp->data += \$value;
break;;
}
\$temp = \$temp->next;
}
if (\$status == 0) {
return;
}
\$new_node = null;
\$per = null;
\$new_node = new MyList(\$level, \$value);
if (\$this->bucket != null) {
\$temp = \$this->bucket;
if (\$temp->order > \$level) {
\$new_node->next = \$this->bucket;
\$this->bucket = \$new_node;
} else {
while (\$temp != null && \$temp->order < \$level) {
\$per = \$temp;
\$temp = \$temp->next;
}
\$new_node->next = \$per->next;
\$per->next = \$new_node;
}
} else {
\$this->bucket = \$new_node;
}
}
public
function removeList() {
\$temp = null;
while (\$this->bucket != null) {
\$temp = \$this->bucket;
\$this->bucket = \$temp->next;
\$temp = null;
}
}
public
}
}
public
function diagonal_sum() {
\$temp = \$this->bucket;
while (\$temp != null) {
echo ("  ". \$temp->data);
\$temp = \$temp->next;
}
}
}

function main() {
\$obj = new BinaryTree();

/* Make A Binary Tree
-----------------------
10
/   \
2     4
/    /  \
3    6    \
/ \    \
1   7    5
/    /
9    3

*/
\$obj->root = new Node(10);
\$obj->root->left = new Node(2);
\$obj->root->left->left = new Node(3);
\$obj->root->right = new Node(4);
\$obj->root->right->right = new Node(5);
\$obj->root->right->left = new Node(6);
\$obj->root->right->left->left = new Node(1);
\$obj->root->right->right->left = new Node(3);
\$obj->root->right->left->right = new Node(7);
\$obj->root->right->left->right->left = new Node(9);
\$obj->get_diagonal(\$obj->root, 0);
\$obj->diagonal_sum();
\$obj->removeList();
}
main();```
```

#### Output

``19 18 13``
``````/*
Node JS Program
Diagonal Sum of a Binary Tree
*/
class Node {

constructor(value) {
this.data = value;
this.left = this.right = null;
}
}
class MyList {

constructor(level, value) {
this.order = level;
this.data = value;
this.next = null;
}
}
class BinaryTree {

constructor() {
this.root = null;
this.bucket = null;
}
var temp = this.bucket;
var status = 1;
while (temp != null) {
if (temp.order == level) {
status = 0;
temp.data += value;
break;;
}
temp = temp.next;
}
if (status == 0) {
return;
}
var new_node = null;
var per = null;
new_node = new MyList(level, value);
if (this.bucket != null) {
temp = this.bucket;
if (temp.order > level) {
new_node.next = this.bucket;
this.bucket = new_node;
} else {
while (temp != null && temp.order < level) {
per = temp;
temp = temp.next;
}
new_node.next = per.next;
per.next = new_node;
}
} else {
this.bucket = new_node;
}
}
removeList() {
var temp = null;
while (this.bucket != null) {
temp = this.bucket;
this.bucket = temp.next;
temp = null;
}
}
}
}
diagonal_sum() {
var temp = this.bucket;
while (temp != null) {
process.stdout.write("  " + temp.data);
temp = temp.next;
}
}

}
function main() {
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
10
/   \
2     4
/    /  \
3    6    \
/ \    \
1   7    5
/    /
9    3

*/
obj.root = new Node(10);
obj.root.left = new Node(2);
obj.root.left.left = new Node(3);
obj.root.right = new Node(4);
obj.root.right.right = new Node(5);
obj.root.right.left = new Node(6);
obj.root.right.left.left = new Node(1);
obj.root.right.right.left = new Node(3);
obj.root.right.left.right = new Node(7);
obj.root.right.left.right.left = new Node(9);
obj.get_diagonal(obj.root, 0);
obj.diagonal_sum();
obj.removeList();
}
main()```
```

#### Output

``19 18 13``
``````/*
Swift 4 Program
Diagonal Sum of a Binary Tree
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;

init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class MyList {
var order: Int;
var data: Int;

var next: MyList? ;
init(_ level: Int, _ value: Int) {
self.order = level;
self.data = value;
self.next = nil;
}
}
class BinaryTree {
var root: Node? ;
var bucket: MyList? ;
init() {
self.root = nil;
self.bucket = nil;
}
func addList(_ level: Int, _ value: Int) {
var temp: MyList? = self.bucket;
var status: Int = 1;
while (temp != nil) {
if (temp!.order == level) {
status = 0;
temp!.data += value;
break;
}
temp = temp!.next;
}
if (status == 0) {
return;
}
var new_node: MyList? = nil;
var per: MyList?  = nil;
new_node = MyList(level, value);
if (self.bucket != nil) {
temp = self.bucket;
if (temp!.order > level) {
new_node!.next = self.bucket;
self.bucket = new_node;
} else {
while (temp != nil && temp!.order < level) {
per = temp;
temp = temp!.next;
}
new_node!.next = per!.next;
per!.next = new_node;
}
} else {
self.bucket = new_node;
}
}
func removeList() {
var temp: MyList? = nil;
while (self.bucket != nil) {
temp = self.bucket;
self.bucket = temp!.next;
temp = nil;
}
}
func get_diagonal(_ head: Node? , _ level : Int) {
}
}
func diagonal_sum() {
var temp: MyList? = self.bucket;
while (temp != nil) {
print( temp!.data, terminator: " ");
temp = temp!.next;
}
}
}
func main() {
let obj: BinaryTree = BinaryTree();
obj.root = Node(10);
obj.root!.left = Node(2);
obj.root!.left!.left = Node(3);
obj.root!.right = Node(4);
obj.root!.right!.right = Node(5);
obj.root!.right!.left = Node(6);
obj.root!.right!.left!.left = Node(1);
obj.root!.right!.right!.left = Node(3);
obj.root!.right!.left!.right = Node(7);
obj.root!.right!.left!.right!.left = Node(9);
obj.get_diagonal(obj.root, 0);
obj.diagonal_sum();
obj.removeList();
}
main();```
```

#### Output

``19 18 13``

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.