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.