text: Find the Alpha Score of the Given Steps ( Using BST ) | C ++ program to implement the above approach ; 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; static long sum = 0 , total_sum = 0 ; static long mod = 1000000007 ; struct Node { Node * left , * right ; int data ; Node ( int x ) { data = x ; left = NULL ; right = NULL ; } } ; long getAlphaScore ( Node * node ) { if ( node -> left != NULL ) getAlphaScore ( node -> left ) ; sum = ( sum + node -> data ) % mod ; total_sum = ( total_sum + sum ) % mod ; if ( node -> right != NULL ) getAlphaScore ( node -> right ) ; return total_sum ; } Node * constructBST ( int arr [ ] , int start , int end , Node * root ) { if ( start > end ) return NULL ; int mid = ( start + end ) / 2 ; if ( root == NULL ) root = new Node ( arr [ mid ] ) ; root -> left = constructBST ( arr , start , mid - 1 , root -> left ) ; root -> right = constructBST ( arr , mid + 1 , end , root -> right ) ; return root ; } int main ( ) { int arr [ ] = { 10 , 11 , 12 } ; int length = 3 ; sort ( arr , arr + length ) ; Node * root = NULL ; root = constructBST ( arr , 0 , length - 1 , root ) ; cout << ( getAlphaScore ( root ) ) ; }