CODEWITHSUNDEEP
javascriptrecursiontreelint
MadHatter
MadHatter

Reputation: 386

JavaScript Recursive Tree Searching Function Not Detecting Nested Children

Trying to make a recursive function that correctly searches the Tree class and all of its descendants for a value and returns true if that value is found, false otherwise.

Of particular importance is the recursive contains() function. Trying to get the code to pass the linter. I'm only getting one error about not detecting nested children. Everything else is passing.

My code:

/* 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;

Here is the file that tests it:

/* 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);
  });
});

And here is the linting error:

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)

Upvotes: 2

Views: 1435

Answers (3)

Chris Tavares
Chris Tavares

Reputation: 30391

Your problem is in this chunk of code here:

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

This line of code will return from the function whatever the result of checkNode is for the first child, true or false. If the result is false you need to continue checking.

Try this instead:

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

Upvotes: 3

Igor Soloydenko
Igor Soloydenko

Reputation: 11775

I think, this is what your code should look like:

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

Upvotes: 2

Blorgbeard
Blorgbeard

Reputation: 103437

You unconditionally return inside the for-loop, so you only check the first child.

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

Should be

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

Upvotes: 2

Related Questions