Here is my code inside a BinarySearchTree class. I don't know if it is because of the behaviour of forEach, or because somewhere in my code is wrong.
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(val) {
let newNode = new Node(val)
if (!this.root) {
this.root = newNode;
return this;
} else {
let level = this.root
// if (val < level.value && level.left){
// level = level.left
while (true) {
if (val < level.value) {
if (level.left) {
level = level.left
} else if (!level.left) {
level.left = newNode;
return this
}
}
else if (val > level.value) {
if (level.right) {
level = level.right
} else if (!level.right) {
level.right = newNode;
return this
}
}
}
}
}
BFS() {
let data = [];
let queue = [];
if (!this.root) {
return false
} else if (this.root) {
queue.push(this.root)
while (queue.length) {
queue.forEach(function (element) {
if (element.left) {
queue.push(element.left)
}
if (element.right) {
queue.push(element.right)
}
queue.shift()
data.push(element)
})
}
return data
}
}
}
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
Here is the input
tree.insert(50)
tree.insert(70)
tree.insert(43)
tree.insert(45)
tree.insert(18)
tree.insert(52)
tree.insert(59)
console.log(tree.BFS())
Here is the output
[
Node {
value: 50,
left: Node { value: 43, left: [Node], right: [Node] },
right: Node { value: 70, left: [Node], right: null }
},
Node {
value: 43,
left: Node { value: 18, left: null, right: null },
right: Node { value: 45, left: null, right: null }
},
Node { value: 18, left: null, right: null },
Node { value: 18, left: null, right: null },
Node { value: 45, left: null, right: null }
]
As you can see, there are duplications and also some nodes of the tree aren't showed at all. Thank everyone in advance!
If you call forEach, you should not modify the underlying array. All kinds of hard-to-understand behavior will result.
As mentioned by @JDB, you should not modify the underlying array in forEach.
Although you don't need to use forEach for BFS in this case as you are only traversing the tree. You can process one element at a time from the front of the queue until the queue is empty.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(val) {
let newNode = new Node(val)
if (!this.root) {
this.root = newNode;
return this;
} else {
let level = this.root
// if (val < level.value && level.left){
// level = level.left
while (true) {
if (val < level.value) {
if (level.left) {
level = level.left
} else if (!level.left) {
level.left = newNode;
return this
}
} else if (val > level.value) {
if (level.right) {
level = level.right
} else if (!level.right) {
level.right = newNode;
return this
}
}
}
}
}
BFS() {
let data = [];
let queue = [];
if (!this.root) {
return false
} else if (this.root) {
queue.push(this.root)
while (queue.length) {
const element = queue[0]
data.push(element)
if (element.left) {
queue.push(element.left)
}
if (element.right) {
queue.push(element.right)
}
queue.shift()
}
return data
}
}
}
const tree = new BinarySearchTree();
tree.insert(50)
tree.insert(70)
tree.insert(43)
tree.insert(45)
tree.insert(18)
tree.insert(52)
tree.insert(59)
const result = tree.BFS()
for (r of result) console.log(r)