Return the average of the values in a given range in a binary search tree.
Example:
[4,11] => avg(6,10,4,9) => return 7.xxThis problem asks you to compute the average of all BST node values that fall within a given inclusive range. The key is to take advantage of the BST property to prune the traversal: if the current value is too small, search only the right subtree; if it is too large, search only the left subtree; otherwise, include it in the sum and count it. A DFS approach with pruning is a natural fit, and the final answer is simply sum divided by count.
END
