I tried to create the insert
method for a binary search tree, but 'this.root' remains null
.
My logic is:
As long as current
(which at the beginning is this.root
) is not null
, continue to update the current
variable, by comparing it with the value we want to insert (if it's greater or less).
When current
is null
, we assign it the new Node:
class Node {
constructor(value){
this.value = value
this.left = null
this.right = null
}
}
class BST {
constructor(){
this.root = null
this.count = 0
}
insert(value){
this.count++
let current = this.root;
while(current){
if(value<current){
current=current.left
}
if(value>current){
current=current.right
}
}
current = new Node(value);
}
}
let Binst = new BST(10);
Binst.insert(22)
Binst.insert(12)
Binst.insert(4)
console.log(Binst)
There are these issues:
Comparing value
with current
is not right: that is comparing a number with an object. You need to compare with current.value
In the main program you call the BST
constructor with an argument, but the constructor does not expect an argument. Although you could adapt the constructor to take that argument, it is better to not pass an argument to the constructor and have an extra call of insert
in your main program.
current = new Node(value)
will not change the tree. It only assigns a new node to a local variable. In order to extend the tree, you need to assign the new node to a left
or right
property of an existing node (or to the root
property of the BST instance). Assigning to a variable never mutates your object structure.
this.root
is never assigned anything else after its initialisation with null
. Again, assigning to current
, is never going to change this.root
.
Because of the previous points, you need to stop your loop one iteration earlier -- when current
points to the node that is about to get a new child. And you also need to deal separately with the case where the new node must become the root of the tree.
The following are just suggestions, not problems:
It is better practice to separate your statements with semicolons. There is the automatic semicolon insertion algorithm, but you wouldn't be the first to fall in one if its traps. Better take control over it yourself.
It is common practice to name variables with an initial capital when they are classes (constructors), but for instances a lower case initial letter is commonly used. So binst
or bIntst
instead of Binst
. I would even suggest a more readable name, like tree
.
Here is the corrected code:
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
this.count = 0;
}
insert(value) {
this.count++;
let current = this.root;
if (!current) {
this.root = new Node(value);
return;
}
while (true) {
if (value < current.value){
if (current.left) {
current = current.left;
} else {
current.left = new Node(value);
return;
}
}
if (value > current.value) {
if (current.right) {
current = current.right;
} else {
current.right = new Node(value);
return;
}
}
}
}
}
let tree = new BST();
tree.insert(10);
tree.insert(22);
tree.insert(12);
tree.insert(4);
console.log(tree);