// Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
      public int size(TreeNode root){
          if(root==null)
              return 0 ;
          return (size(root.left)+size(root.right)+root.val);
          
      }
  }

class Solution {
    TreeNode parentNode ;boolean flag  = true ;
    public TreeNode bstToGst(TreeNode root) {
     if(flag){
         parentNode = root;flag  = false ;}
        if(root==null)
        return null;
   
        TreeNode root1 = new TreeNode(root.val+findMax(parentNode,root.val));
        // System.out.println(root1.val);
        root1.left=bstToGst(root.left);
        root1.right=bstToGst(root.right);
        return root1 ;
    
    
    }
    public int findMax(TreeNode root,int k ){
        if(root==null)
            return  0 ;
        if(root.val<k){
            return(findMax(root.right,k));
        }
        else if(root.val>k){
            int sum = 0;
            
             if(root.right == null)
                sum = root.val;
            else
               sum= root.val+root.right.size(root.right);
        return(sum+findMax(root.left,k));
        }
        else{
            if(root.right == null)
                return 0;
            return root.right.size(root.right);
    }
    }
}