Recursion to traverse all the nested child nodes of Binary Tree Javascript

Question

I am playing around with a binary tree. I am trying to use recursion to find all the nested children's values and push all the values into an array. I started with the left tree to see if it works. I tried to call childrenArray() but the console says childrenArray() is not defined. When I ask if (typeof BinaryTree.prototype.childrenArray === 'function'), it returns true. Please teach me and tell me why I wasn't able to execute my code?

var Tree = function(value) {
  if (!(this instanceof Tree)) {
    return new Tree(value);
  }
  this.value = value;
  this.children = [];
};

Tree.prototype.addChild = function(value) {
  var child = new Tree(value);
  this.children.push(child);
};

Tree.prototype.contains = function(value) {
  if (this.value === value) {
    return true;
  } else {
    for (var i = 0; i < this.children.length; i++) {
      if (this.children[i] && this.children[i].contains(value)) {
        return true;
      }
    }
    return false;
  }
};


var BinaryTree = function(value) {
  if (!(this instanceof BinaryTree)) {
    return new BinaryTree(value);
  }
  Tree.call(this, value);
};
BinaryTree.prototype = Object.create(Tree.prototype);

BinaryTree.prototype.addChild = function(value) {
  if (value < this.value) {
    if (this.children[0] === undefined) {
      this.children[0] = new BinaryTree(value);
    }
    this.children[0].addChild(value);
  } else if (value > this.value) {
    if (this.children[1] === undefined) {
      this.children[1] = new BinaryTree(value);
    }
    this.children[1].addChild(value);
  }
};
BinaryTree.prototype.contains = function(value) {
  if (value < this.value) {
    if (this.children[0] === undefined) {
      return false;
    }
    return this.children[0].contains(value);
  } else if (value > this.value) {
    if (this.children[1] === undefined) {
      return false;
    }
    return this.children[1].contains(value);
  }
};

var a = new BinaryTree();
a.value = 10;
a.addChild(4);
a.addChild(11);
a.addChild(3);

BinaryTree.prototype.childrenArray = function() {
  var results = [];

  if (this.value) {
    results.push(this.value);
  }

  if (this.children[0].length === 0) {

    return results;
  }

  for (var i = 0; i < this.children[0].children.length; i++) {
    if (this.children[i].value) {
      results.push(this.children[i].value);
      return this.childrenArray();
    }
  }

};

a.childrenArray();

You have defined `childrenArray()`, but not `childArray()`. Think you are confusing the two. — leoOrion, Jun 06 '16 at 01:51
Have you replaced `childArray` with `this.childrenArray`? If you call childrenArray on the same object it will start to recurse infinitly. Even so, have a _good_ look at how you plan to pass `results` from one level of recursion to another. — traktor, Jun 06 '16 at 02:27

score 1 · Accepted Answer · edited May 23 '17 at 12:15

As @melpomene mentioned, you are invoking childArray but you didn't define it anywhere. I assume the line return childArray(); ended up there by mistake, you probably meant to recursively return childrenArray for the left child of root.

I would like to mention that your loop itself (without the recursive call):

for(var i = 0; i < this.children[0].children.length; i++) { // <-- you are iterating over the children of root's left child
     if(this.children[i].value) { // <-- but you are accessing root's current child
        results.push(this.children[i].value);
     }
}

is somewhat confusing. You are iterating over the children of root's left child children[0].children, but on each iteration you check if the root's children themselves children[i] have a value and you push that value. This is incorrect and will break if, for example, the root only has a left child that has both children (i will be out of bounds).

Here's how you can approach this problem. The recursion to print the left tree in your case can be broken down into the following cases:

If the current node has no value, return an empty array
Else If the current node has no children, return an array only containing the current value
Else if the current node has a left child, run childrenArray on it recursively and add the results to the results array

Here's how that would look:

BinaryTree.prototype.childrenArray = function() {
  var results = [];

  // case 1:
  if (this.value === undefined) {
    return results;
  }

  // case 2:
  results.push(this.value);
  if (this.children.length === 0) {
    return results;
  }

  // case 3:
  var leftChild = this.children[0];
  if (leftChild) {
    results = results.concat(leftChild.childrenArray());
  }

  /* add code here for the right child to complete your function */

  return results;
};

Full Example:

var BinaryTree = function(value) {
  this.value = value;
  this.children = [];
};

BinaryTree.prototype.addChild = function (value) {
  if (value < this.value) {
    if (this.children[0] === undefined) {
      this.children[0] = new BinaryTree(value);
    }
    this.children[0].addChild(value);
  } else if (value > this.value) {
    if (this.children[1] === undefined) {
      this.children[1] = new BinaryTree(value);
    }
    this.children[1].addChild(value);
  }
};

BinaryTree.prototype.childrenArray = function() {
  var results = [];

  // case 1:
  if (this.value === undefined) {
    return results;
  }

  // case 2:
  results.push(this.value);
  if (this.children.length === 0) {
    return results;
  }

  // case 3:
  var leftChild = this.children[0];
  if (leftChild) {
    results = results.concat(leftChild.childrenArray());
  }

  /* add code here for the right child to complete your function */

  return results;
};

var a = new BinaryTree(10);
a.addChild(4);
a.addChild(11);
a.addChild(3);

console.log(a.childrenArray()); // [10, 4, 3]

Last thing, based on your insertion logic (insert left if smaller, right if larger), you are building a Binary Search Tree not a Binary Tree. Binary tree's don't follow any particular insertion logic. Take a look at this question for clarification

thanks! Can you explain why we using concat instead of push. And why does it concat the value when this -> this.children[0] = {value: 1: child:[]}; it is an object. Because I thought this.children[0].value will get the value. — spaceDog, Jun 06 '16 at 03:51
You're welcome. Since `childrenArray()` returns an array and you want to push the contents of that array into the `results` array, doing `results.push(content)` would add the whole array as a single element into `results` but you want all the elements from the array instead. [`[].concat`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/concat) combines two arrays into a single array, which is what you want. — nem035, Jun 06 '16 at 04:01

Recursion to traverse all the nested child nodes of Binary Tree Javascript

1 Answers1