Diagonal Sum of a Binary Tree | C ++ Program to calculate the sum of diagonal nodes . ; Node Structure ; to map the node with level - index ; Function to create new node ; recursvise function to calculate sum of elements where level - index is same . ; if there is no child then return ; add the element in the group of node whose level - index is equal ; left child call ; right child call ; Function call ; for different values of level - index add te sum of those node to answer ; Driver code ; build binary tree ; Function Call ; print the daigonal sums
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; map < int , int > grid ; struct Node * newNode ( int data ) { struct Node * Node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; Node -> data = data ; Node -> left = Node -> right = NULL ; return Node ; } void addConsideringGrid ( Node * root , int level , int index ) { if ( root == NULL ) return ; grid [ level - index ] += ( root -> data ) ; addConsideringGrid ( root -> left , level + 1 , index - 1 ) ; addConsideringGrid ( root -> right , level + 1 , index + 1 ) ; } vector < int > diagonalSum ( Node * root ) { grid . clear ( ) ; addConsideringGrid ( root , 0 , 0 ) ; vector < int > ans ; for ( auto x : grid ) { ans . push_back ( x . second ) ; } return ans ; } int main ( ) { struct Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 9 ) ; root -> left -> right = newNode ( 6 ) ; root -> right -> left = newNode ( 4 ) ; root -> right -> right = newNode ( 5 ) ; root -> right -> left -> right = newNode ( 7 ) ; root -> right -> left -> left = newNode ( 12 ) ; root -> left -> right -> left = newNode ( 11 ) ; root -> left -> left -> right = newNode ( 10 ) ; vector < int > v = diagonalSum ( root ) ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) cout << v [ i ] << " ▁ " ; return 0 ; }