Programming: Binary Search Trees One of the data structures…

Programming: Binary Search Trees One of the data structures we studied was binary search trees. A simple implementation of node for a binary tree where keys are integers is shown below – your answer must be in terms of it. private class Node {    public final Integer key;    public final Value val;    public Node left, right;    public int N;    public Node(Key key, Value val, int N) {        this.key = key;        this.val = val;         this.N = N;    }} Implement the recursive method public static int countLeafSums(Node root, int sum) that counts the number of root to leaf paths that sum to a specific value. The sum is taken on the keys. Consider the example tree below: countLeafSums(root, 17) returns 0, countLeafSums(root, 34) returns 2, and countLeafSums(root, 47) returns 1. Creating additional helper methods is fine but you should provide a one line comment that indicates their purpose. No packages may be imported. public static int countLeafSums(Node root, int sum) {  //TODO: IMPLEMENT ME.