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!
CodePudding user response:
If you call forEach
, you should not modify the underlying array. All kinds of hard-to-understand behavior will result.
CodePudding user response:
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)