Replace each node of a Binary Tree with the sum of all the nodes present in its diagonal | CPP program to implement the above approach ; Structure of a tree node ; Function to replace each node with the sum of nodes at the same diagonal ; IF root is NULL ; Replace nodes ; Traverse the left subtree ; Traverse the right subtree ; Function to find the sum of all the nodes at each diagonal of the tree ; If root is not NULL ; If update sum of nodes at current diagonal ; Traverse the left subtree ; Traverse the right subtree ; Function to print the nodes of the tree using level order traversal ; Stores node at each level of the tree ; Stores count of nodes at current level ; Stores front element of the queue ; Insert left subtree ; Insert right subtree ; Update length ; Driver Code ; Build tree ; Store sum of nodes at each diagonal of the tree ; Find sum of nodes at each diagonal of the tree ; Replace nodes with the sum of nodes at the same diagonal ; Print tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TreeNode { int val ; struct TreeNode * left , * right ; TreeNode ( int x ) { val = x ; left = NULL ; right = NULL ; } } ; void replaceDiag ( TreeNode * root , int d , unordered_map < int , int > & diagMap ) { if ( ! root ) return ; root -> val = diagMap [ d ] ; replaceDiag ( root -> left , d + 1 , diagMap ) ; replaceDiag ( root -> right , d , diagMap ) ; } void getDiagSum ( TreeNode * root , int d , unordered_map < int , int > & diagMap ) { if ( ! root ) return ; if ( diagMap [ d ] > 0 ) diagMap [ d ] += root -> val ; else diagMap [ d ] = root -> val ; getDiagSum ( root -> left , d + 1 , diagMap ) ; getDiagSum ( root -> right , d , diagMap ) ; } void levelOrder ( TreeNode * root ) { queue < TreeNode * > q ; q . push ( root ) ; while ( true ) { int length = q . size ( ) ; if ( ! length ) break ; while ( length ) { auto temp = q . front ( ) ; q . pop ( ) ; cout << temp -> val << " ▁ " ; if ( temp -> left ) q . push ( temp -> left ) ; if ( temp -> right ) q . push ( temp -> right ) ; length -= 1 ; } } } int main ( ) { TreeNode * root = new TreeNode ( 5 ) ; root -> left = new TreeNode ( 6 ) ; root -> right = new TreeNode ( 3 ) ; root -> left -> left = new TreeNode ( 4 ) ; root -> left -> right = new TreeNode ( 9 ) ; root -> right -> right = new TreeNode ( 2 ) ; unordered_map < int , int > diagMap ; getDiagSum ( root , 0 , diagMap ) ; replaceDiag ( root , 0 , diagMap ) ; levelOrder ( root ) ; return 0 ; }