Курс: "Введение в ООП" (Хекслет)

Мое решение 1

/

Решение учителя

/

Испытание 4: Сбалансированное двоичное дерево

Особенность структуры двоичного дерева даёт хороший прирост к эффективности при поиске нужного значения. Для этого нужно, чтобы двоичное дерево было сбалансированным. То есть необходимо построить дерево так, чтобы общее количество узлов в левом и правом поддеревьях было примерно одинаковым для любого узла дерева.

Node.js
Реализуйте метод isBalanced(), который проверяет дерево на сбалансированность. Он возвращает true, если количество узлов в левом и правом поддеревьях каждого узла отличается не более, чем на 2. В ином случае метод должен вернуть false.

Сбалансированное дерево

Сбалансированное двоичное дерево поиска

Несбалансированное дерево

Несбалансированное двоичное дерево поиска

В узле 5 количество узлов в левом поддереве равно 4, а в правом — 1. Разница составляет 3. Это больше, чем максимально допустимая разница по условию задачи (2).

Примеры
const tree1 = new Node(4,
  new Node(3,
    new Node(2)));

tree1.isBalanced(); // true

const tree2 = new Node(4,
  new Node(3,
    new Node(2,
      new Node(1))));

tree2.isBalanced(); // false