Diagonal Sum of a Binary Tree | Python3 program calculate the sum of diagonal nodes . ; A binary tree node structure ; To map the node with level - index ; 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
from collections import deque NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT grid = { } NEW_LINE def addConsideringGrid ( root , level , index ) : NEW_LINE INDENT global grid NEW_LINE if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT grid [ level - index ] = ( grid . get ( level - index , 0 ) + root . data ) NEW_LINE addConsideringGrid ( root . left , level + 1 , index - 1 ) NEW_LINE addConsideringGrid ( root . right , level + 1 , index + 1 ) NEW_LINE DEDENT def diagonalSum ( root ) : NEW_LINE INDENT addConsideringGrid ( root , 0 , 0 ) NEW_LINE ans = [ ] NEW_LINE for x in grid : NEW_LINE INDENT ans . append ( grid [ x ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( 1 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 3 ) NEW_LINE root . left . left = Node ( 9 ) NEW_LINE root . left . right = Node ( 6 ) NEW_LINE root . right . left = Node ( 4 ) NEW_LINE root . right . right = Node ( 5 ) NEW_LINE root . right . left . right = Node ( 7 ) NEW_LINE root . right . left . left = Node ( 12 ) NEW_LINE root . left . right . left = Node ( 11 ) NEW_LINE root . left . left . right = Node ( 10 ) NEW_LINE v = diagonalSum ( root ) NEW_LINE for i in v : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT