spaceDog - 2 years ago 170

Javascript Question

I am playing around with a binary tree. I am trying to use recursion to find all the nested children's value and push all the values into an array. I started with the left tree to see if it works. I tried to call

`childrenArray()`

`if(typeof BinaryTree.prototype.childrenArray === 'function')`

`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();

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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(this.children[0].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(this.children[0].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

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**