Replace each node of a Binary Tree with the sum of all the nodes present in its diagonal | 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
class TreeNode : NEW_LINE INDENT def __init__ ( self , val = 0 , left = None , right = None ) : NEW_LINE INDENT self . val = val NEW_LINE self . left = left NEW_LINE self . right = right NEW_LINE DEDENT DEDENT def replaceDiag ( root , d , diagMap ) : NEW_LINE INDENT if not root : NEW_LINE INDENT return NEW_LINE DEDENT root . val = diagMap [ d ] NEW_LINE replaceDiag ( root . left , d + 1 , diagMap ) NEW_LINE replaceDiag ( root . right , d , diagMap ) NEW_LINE DEDENT def getDiagSum ( root , d , diagMap ) : NEW_LINE INDENT if not root : NEW_LINE INDENT return NEW_LINE DEDENT if d in diagMap : NEW_LINE INDENT diagMap [ d ] += root . val NEW_LINE DEDENT else : NEW_LINE INDENT diagMap [ d ] = root . val NEW_LINE DEDENT getDiagSum ( root . left , d + 1 , diagMap ) NEW_LINE getDiagSum ( root . right , d , diagMap ) NEW_LINE DEDENT def levelOrder ( root ) : NEW_LINE INDENT que = [ root ] NEW_LINE while True : NEW_LINE INDENT length = len ( que ) NEW_LINE if not length : NEW_LINE INDENT break NEW_LINE DEDENT while length : NEW_LINE INDENT temp = que . pop ( 0 ) NEW_LINE print ( temp . val , end = ' ▁ ' ) NEW_LINE if temp . left : NEW_LINE INDENT que . append ( temp . left ) NEW_LINE DEDENT if temp . right : NEW_LINE INDENT que . append ( temp . right ) NEW_LINE DEDENT length -= 1 NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = TreeNode ( 5 ) NEW_LINE root . left = TreeNode ( 6 ) NEW_LINE root . right = TreeNode ( 3 ) NEW_LINE root . left . left = TreeNode ( 4 ) NEW_LINE root . left . right = TreeNode ( 9 ) NEW_LINE root . right . right = TreeNode ( 2 ) NEW_LINE diagMap = { } NEW_LINE getDiagSum ( root , 0 , diagMap ) NEW_LINE replaceDiag ( root , 0 , diagMap ) NEW_LINE levelOrder ( root ) NEW_LINE DEDENT