BST Maximum Difference.java

//{ Driver Code Starts
import java.io.*;
import java.util.*;

class Node{
    int data;
    Node left;
    Node right;
    Node(int data){
        this.data = data;
        left=null;
        right=null;
    }
}

class GFG {
    
	public static void main (String[] args) throws Exception{
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        
	        int t=Integer.parseInt(br.readLine());
	        while(t > 0){
	            int n=Integer.parseInt(br.readLine().trim());
	            String s[] = br.readLine().trim().split(" ");

	            int target=Integer.parseInt(br.readLine().trim());
    	    	Node root = null;
                for(int i=0;i<n;i++){
                    root=insert(root,Integer.parseInt(s[i]));
                }
        	    Solution g = new Solution();
        	    System.out.println(g.maxDifferenceBST(root,target));
                t--;
            
        }
    }

    public static Node insert(Node tree, int val) {
        Node temp = null;
        if (tree == null) return new Node(val);
    
        if (val < tree.data) {
            tree.left = insert(tree.left, val);
        } else if (val > tree.data) {
            tree.right = insert(tree.right, val);
        }
    
        return tree;
    }
  
}
// } Driver Code Ends


//User function Template for Java

class Solution
{
    public static int maxDifferenceBST(Node root,int target)
    {
        //Please code here
        int rootsum=0,
        leafsum=0;
        while(root!=null)
        {
            rootsum+=root.data;
            if(target==root.data)
            break;
            if(target<root.data)
            root=root.left;
            else
            root=root.right;
        }
        if(root==null)
        return -1;
        leafsum=minPath(root);
        return rootsum-leafsum;
    }
    
    private static int minPath( Node root)
    {
        if(root==null)
        return 0;
        int sum=root.data;
        if(root.left==null)
        sum+=minPath(root.right);
        else if(root.right== null)
        sum+=minPath(root.left);
        else
        sum+=Math.min(minPath(root.left),minPath(root.right));
        return sum;
    }
}