Сумма элементов бинарного дерева поиска в диапазоне значение

Задача.

Дано бинарное дерево поиска. Нужно найти сумму всех вершин этого дерева, значения которых лежит в диапазоне значений от low до high включительно.
Например, для дерева

Сумма элементов в диапазоне от 7 до 15, равна 10 + 7 + 15 = 32

Решение.

Бинарное или Двоичное Дерево Поиска это двоичное дерево, у которого значения во всех вершинах левого поддерева меньше или равны значению в самой вершине, а значения во всех вершинах правого поддерева строго больше значения в самой вершине. Более того, левое и правое поддерево являются двоичными деревьями поиска. Т.е. это свойство выполняется рекурсивно. Свойства для значений вершин соблюдается для всех поддеревьев.

Класс вершины двоичного дерева:

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;
    }
 }

По сути, нам нужно просто обойти дерево и просуммировать все элементы, значения которых лежат в заданных пределах.
Для обхода дерева воспользуемся pre-order алгоритмом обхода двоичного дерева.

public static void dfs(BinaryTree tree) {
  if (tree == null) {
    return;
  }
  visit(tree);
  dfs(tree.left);
  dfs(tree.right);
}

Вместо visit нам нужно добавить логику на проверку того, что значение лежит в нужном диапазоне и добавить значение к сумме:

    //Если значение в заданном диапазоне, то добавляем его к сумме
    if (root.val >= low && root.val <= high) {
        sum += root.val;
    }

Т.к. у нас в условии дано Двоичное Дерево Поиска, то мы можем сократить число рекурсивных вызовов для поддеревьев.
Например, для дерева из примера, если мы находимся в вершине 5, то делать рекурсивный вызов для левого поддерева не имеет смысл, т.к. там по определению Бинарного Дерева Поиска все значения меньше или равны 5. А у нас диапазон от 7 до 15. Т.е. искать в левом поддереве не имеет смысла, если значение в вершине меньше нижней границы заданного диапазона.
Аналогично для правого поддерева, там искать нет смысла, если значение в вершине больше верхнего предела заданного диапазона. Т.к. по определению Бинарного Дерева Поиска там все значения больше, чем в текущей вершине, а значит лежат за пределами нашего диапазона.

Тогда финальное решение выглядит так:

public int rangeSumBST(TreeNode root, int low, int high) {
    //base-case
    if (root == null) {
        return 0;
    }
    int sum = 0;

    //Если значение в заданном диапазоне, то добавляем его к сумме
    if (root.val >= low && root.val <= high) {
        sum += root.val;
    }

    //В левое поддерево имеет смысл идти только, когда нижняя 
    //граница меньше значения в текущей вершине
    if (low < root.val) {
        sum += rangeSumBST(root.left, low, high);
    }
    //В правое поддерево имеет смысл идти только, когда верхняя 
    //граница больше значения в текущей вершине
    if (high > root.val) {
        sum += rangeSumBST(root.right, low, high);
    }
    return sum;
}