Maximum sum from a tree with adjacent levels not allowed | Python3 code for max sum with adjacent levels not allowed ; A BST node ; Recursive function to find the maximum sum returned for a root node and its grandchildren ; Returns maximum sum with adjacent levels not allowed . This function mainly uses getSumAlternate ( ) ; We compute sum of alternate levels starting first level and from second level . And return maximum of two values . ; Driver code
from collections import deque as queue NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def getSumAlternate ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT sum = root . data NEW_LINE if ( root . left != None ) : NEW_LINE INDENT sum += getSum ( root . left . left ) NEW_LINE sum += getSum ( root . left . right ) NEW_LINE DEDENT if ( root . right != None ) : NEW_LINE INDENT sum += getSum ( root . right . left ) NEW_LINE sum += getSum ( root . right . right ) NEW_LINE DEDENT return sum NEW_LINE DEDENT def getSum ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return max ( getSumAlternate ( root ) , ( getSumAlternate ( root . left ) + getSumAlternate ( root . right ) ) ) 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 . right . left = Node ( 4 ) NEW_LINE root . right . left . right = Node ( 5 ) NEW_LINE root . right . left . right . left = Node ( 6 ) NEW_LINE print ( getSum ( root ) ) NEW_LINE DEDENT