Сумма элементов бинарного дерева поиска в диапазоне значение
Published: 2023-09-25 20:09:56

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uych7r6jkcwnd7si5ydl.png)



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

## Решение.

Бинарное или [Двоичное Дерево Поиска](https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0) это двоичное дерево, у которого значения во **всех** вершинах левого поддерева меньше или равны значению в самой вершине, а значения во всех вершинах правого поддерева строго больше значения в самой вершине. Более того, левое и правое поддерево являются двоичными деревьями поиска. Т.е. это свойство выполняется рекурсивно. Свойства для значений вершин соблюдается для всех поддеревьев. 

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

```java
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 алгоритмом обхода двоичного дерева](https://dev.to/faangmaster/alghoritmy-obkhoda-dvoichnogho-dierieva-26l4).

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

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

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

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

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

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

```