"Cracking the coding interview", Trees and Graphs, 4.2

cracking-the-coding-interview-4-2.js

/**
 * Конструктор узла дерева.
 * Каждый узел имеет 2 ссылки: левую и правую части поддерева.
 */
class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

/**
 * По переданному отсортированному массиву
 * создается сбалансированное дерево бинарного поиска
 */
function createBalancedTree(arr) {
  return _createBalancedTree(arr, 0, arr.length - 1);
}

/**
 * Рекурсивно создает узлы для каждой «половинки» массива:
 * левая и правые части превращаются в соответствующие поддеревья
 */
function _createBalancedTree(arr, start, end) {
  if (end < start) {
    return null;
  }
  const mid = Math.floor((start + end) / 2);
  const node = new Node(arr[mid]);
  
  node.left = _createBalancedTree(arr, start, mid - 1);
  node.right = _createBalancedTree(arr, mid + 1, end);
  
  return node;
}