Find the Alpha Score of the Given Steps ( Using BST ) | Structure of a node ; Function to calculate and return the Alpha Score of the journey ; Traverse left subtree ; Calculate the alpha score of the current step ; Update alpha score of the journey ; Traverse right subtree ; Return ; Function to construct a BST from the sorted array arr [ ] ; Insert root ; Construct left subtree ; Construct right subtree ; Return root ; Driver code ; Sort the array ; Construct BST from the sorted array
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT sum = 0 NEW_LINE total_sum = 0 NEW_LINE mod = 1000000007 NEW_LINE def getAlphaScore ( node ) : NEW_LINE INDENT global sum NEW_LINE global total_sum NEW_LINE if node . left != None : NEW_LINE INDENT getAlphaScore ( node . left ) NEW_LINE DEDENT sum = ( sum + node . data ) % mod NEW_LINE total_sum = ( total_sum + sum ) % mod NEW_LINE if node . right != None : NEW_LINE INDENT getAlphaScore ( node . right ) NEW_LINE DEDENT return total_sum NEW_LINE DEDENT def constructBST ( arr , start , end , root ) : NEW_LINE INDENT if start > end : NEW_LINE INDENT return None NEW_LINE DEDENT mid = ( start + end ) // 2 NEW_LINE if root == None : NEW_LINE INDENT root = Node ( arr [ mid ] ) NEW_LINE DEDENT root . left = constructBST ( arr , start , mid - 1 , root . left ) NEW_LINE root . right = constructBST ( arr , mid + 1 , end , root . right ) NEW_LINE return root NEW_LINE DEDENT arr = [ 10 , 11 , 12 ] NEW_LINE length = len ( arr ) NEW_LINE arr . sort ( ) NEW_LINE root = None NEW_LINE root = constructBST ( arr , 0 , length - 1 , root ) NEW_LINE print ( getAlphaScore ( root ) ) NEW_LINE