Функция рекурсивного поиска по JavaScript не обнаруживает вложенных потомков

Question

Попытка создать рекурсивную функцию, которая корректно ищет класс Tree и всех его потомков для значения и возвращает true, если это значение найдено, в противном случае - false.

Особое значение имеет рекурсивная функция contains(). Попытка получить код для передачи линтера. У меня только одна ошибка из-за того, что я не обнаружил вложенных детей. Все остальное проходит.

Мой код:

/* eslint-disable no-trailing-spaces */
/* eslint-disable no-unused-vars */
class Tree {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  // Adds a new Tree node with the input value to the current Tree node 
  addChild(value) {
    this.children.push(new Tree(value));
  }
  // Checks this node's children to see if any of them matches the given value
  // Continues recursively until the value has been found or all of the children
  // have been checked
  contains(value) {
    const thisNode = this;
    function checkNode(node) {
      if (node.value === value) {
        return true;
      }
      if (node.children.length > 0) {
        for (let i = 0; i < node.children.length; i++) {
          return checkNode(node.children[i]);
        }
      }
      return false;
    }
    return checkNode(thisNode);
  }
}

module.exports = Tree;

Вот файл, который проверяет это:

/* eslint-disable no-undef */
const Tree = require('../src/tree');

describe('Tree', () => {
  let tree;

  beforeEach(() => {
    tree = new Tree(true);
  });

  it('should have methods named "addChild" and "contains"', () => {
    expect(typeof tree.addChild).toBe('function');
    expect(typeof tree.contains).toBe('function');
  });

  it('should add children to the tree', () => {
    tree.addChild(5);
    expect(tree.children[0].value).toBe(5);
  });

  it('should return true for a value that the tree contains', () => {
    tree.addChild(5);
    expect(tree.contains(5)).toBe(true);
  });

  it('should return false for a value that was not added', () => {
    tree.addChild(5);
    expect(tree.contains(6)).toBe(false);
  });

  it('should be able to add children to a tree\'s child', () => {
    tree.addChild(5);
    tree.children[0].addChild(6);
    expect(tree.children[0].children[0].value).toBe(6);
  });

  it('should correctly detect nested children', () => {
    tree.addChild(5);
    tree.addChild(6);
    tree.children[0].addChild(7);
    tree.children[1].addChild(8);
    expect(tree.contains(7)).toBe(true);
    expect(tree.contains(8)).toBe(true);
  });
});

А вот и ошибка linting:

Tree
    ✓ should have methods named "addChild" and "contains" (5ms)
    ✓ should add children to the tree (1ms)
    ✓ should return true for a value that the tree contains (3ms)
    ✓ should return false for a value that was not added (1ms)
    ✓ should be able to add children to a tree's child (1ms)
    ✕ should correctly detect nested children (9ms)

Answer 1

Вы безоговорочно возвращаетесь в цикл for, поэтому проверяете только первого потомка.

    for (let i = 0; i < node.children.length; i++) {
      return checkNode(node.children[i]);
    }

Должно быть

    for (let i = 0; i < node.children.length; i++) {
      if (checkNode(node.children[i])) return true;
    }

Answer 2

Ваша проблема в этом куске кода здесь:

  if (node.children.length > 0) {
    for (let i = 0; i < node.children.length; i++) {
      return checkNode(node.children[i]);
    }
  }

Эта строка кода будет возвращаться из функции независимо от результата checkNode для первого потомка, true или false. Если результат ложный, вам нужно продолжить проверку.

Попробуйте это вместо этого:

  if (node.children.length > 0) {
    for (let i = 0; i < node.children.length; i++) {
      if (checkNode(node.children[i])) {
        return true;
      }
    }
  }

Answer 3

Я думаю, вот как должен выглядеть ваш код:

for (let childIndex = 0; childIndex < node.children.length; childIndex++) {
   const foundInChildren = checkNode(node.children[childIndex]);
   if (foundInChildren)
     return true;
}