BinaryTree/diagonal_sum_of_a_binary_tree.cpp at master · arpansahu/BinaryTree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <malloc.h>
/* nodes for queue and tree node*/
struct node {
    int key;
    struct node * left;
    struct node * right;
};

/* function for creating new node of tree*/
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->key = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}


/*building a map for storing a pair and key */

struct  mapinc{
    int key ;
    int sum;
    struct mapinc * next;
};
struct mapinc * mapper = NULL;

void insertInMap(int sum,int key){
    struct mapinc *  temp = (struct mapinc *) malloc(sizeof(struct mapinc));
    temp->key =  key;
    temp->sum = sum;
    temp->next = NULL;
    int condition = 1;
    if(mapper == NULL){
        mapper = temp;
    } else{
        struct mapinc *  iter =  mapper;
        while(iter != NULL && condition){

            if(iter->key == temp->key){
                condition = 0;
                iter->sum = iter->sum + temp->sum;
                return ;

            }
            iter = iter->next;

        }
        if(condition == 1){
            temp->next = mapper;
            mapper = temp;
        }
    }

}


void viewmap(){

    struct mapinc *  iter =  mapper;
    if(iter == NULL){
        return;
    }
    while(iter != NULL){
        printf("%d ",iter->sum);
        iter = iter->next;
    }


}


/*function for level order traversal iteratively*/
void verticalTraversalOfTheTreeRecursively(node *root, int diagonal)
{
    if (root == nullptr)
        return;
    insertInMap(root->key,diagonal);
    verticalTraversalOfTheTreeRecursively(root->left,diagonal +1);
    verticalTraversalOfTheTreeRecursively(root->right, diagonal);
}
void diagonalSum(node * root){
    verticalTraversalOfTheTreeRecursively(root, 0);
    viewmap();

}

int main(){
    node* root = newNode(1);

    /* Construct below tree
              1
            /  \
           /    \
          2      3
         /     /  \
        /     /    \
       4     5     6
            / \
           /   \
          7     8
    */


    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->left = newNode(7);
    root->right->left->right = newNode(8);

    diagonalSum(root);

    return 0;
}