Find the Alpha Score of the Given Steps ( Using BST ) | Java 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
import java . lang . * ; import java . util . * ; class Node { Node left , right ; int data ; public Node ( int data ) { this . data = data ; left = null ; right = null ; } } class AlphaScore { Node root ; AlphaScore ( ) { root = null ; } static long sum = 0 , total_sum = 0 ; static long mod = 1000000007 ; public static 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 ; } public static 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 ; } public static void main ( String args [ ] ) { int arr [ ] = { 10 , 11 , 12 } ; int length = arr . length ; Arrays . sort ( arr ) ; Node root = null ; root = constructBST ( arr , 0 , length - 1 , root ) ; System . out . println ( getAlphaScore ( root ) ) ; } }