JavaScript;Функция validateBinaryTree выдает ошибку значения на узле

Question

Задача кодирования, в которой мы должны написать функцию, которая определяет, допустимо ли двоичное дерево.Дерево - это просто коллекция BinaryTreeNode, которые связаны между собой вручную.Функция validateBinaryTree должна возвращать false, если какие-либо значения в левом поддереве больше корневого значения, или false, если какие-либо значения в правом поддереве меньше, и true в противном случае.

Здесь указан класс BinaryTreeNode:

class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insertLeft(value) {
    this.left = new BinaryTreeNode(value);
    return this.left;
  }

  insertRight(value) {
    this.right = new BinaryTreeNode(value);
    return this.right;
  }

  depth_first_print() {
    console.log(this.value);
    if (this.left) {
      this.left.depth_first_print();
    }
    if (this.right) {
      this.right.depth_first_print();
    }
  }

}

Вот функция validateBinaryTree:

const validateBinaryTree = (rootNode) => {
  const rootValue = rootNode.value;
  let isValid = true;
  const validateLeft = (node) => {
    if (node.value > rootValue) isValid = false;
    if (node.left) {
      validateLeft(node.left);
    }
    if (node.right) {
      validateLeft(node.right);
    }
  }
  const validateRight = (node) => {
    if (node.value < rootValue) isValid = false;
    if (node.left) {
      validateRight(node.left);
    }
    if (node.right) {
      validateRight(node.right);
    }
  }
  validateLeft(rootNode.left);
  validateRight(rootNode.right);
  return isValid;
}


//Build an invalid binary tree which will look like this:
//    10
//   /
//  50

const tree = new BinaryTreeNode(10);
tree.insertLeft(50);

Следующий вызов функции должен вывести на консоль false:

console.log(validateBinaryTree(tree));

Но вместо этого яполучить следующую ошибку:

if (node.value < rootValue) isValid = false;
             ^

TypeError: Cannot read property 'value' of null

Answer 1

Ваш исходный код завершается ошибкой, потому что вы пытаетесь вызвать validateRight для rootNode.right, то есть null.Вот почему на самом деле лучше поместить эту проверку (против node === null case) внутри самого валидатора.

Кроме того, я бы упростил этот код, передав две отдельные функции внутрь - одну для левой ветви, другую для правой- закрывается на rootNode значение.Например:

const validateBinaryTree = (rootNode) => {
  const forLeft  = val => val < rootNode.value;
  const forRight = val => val > rootNode.value;

  const validateBranch = (node, branchComparator) => {
    return node === null || 
      branchComparator(node.value) &&
      validateBranch(node.left, branchComparator) && 
      validateBranch(node.right, branchComparator);
  }

  return validateBranch(rootNode.left, forLeft) && validateBranch(rootNode.right, forRight);
}

Эта версия также имеет (небольшое) преимущество немедленной остановки проверки при обнаружении сбойного узла (из-за природы короткого замыкания оператора && в JS).