I’m currently working on the odin project on Binary Search Tree. I’m trying to make deleteNode work, and I’m working on removing a node if it is a leaf node.
Here’s my code:
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
buildTree(array) {
//accepts an array of integers and sort them into binary search tree;
//loop through the given array, creating a node for each item. insert nodes into the array in a binarySearchTree manner.
array.forEach((item) => {
this.insert(item);
});
}
insert(value) {
//accepts an integer value and sort it into the tree;
let newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
return this;
}
current = current.left;
} else if (value > current.value) {
if (current.right === null) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
deleteNode(value) {
let current = this.root;
let prev;
if (!current) {
console.log("hello");
return undefined;
}
while (current) {
if (current.value > value) {
prev = current;
current = current.left;
} else if (current.value < value) {
prev = current;
current = current.right;
} else {
//node found.
//case 1: node is leaf node, no left and right children
if (!current.left && !current.right) {
if (prev.value > current.value) {
prev.left = null;
} else {
prev.right = null;
}
console.log("leaf node deleted", current);
return this;
}
//case 2: node has either left or right child
//case 3: node has both left and right children
}
}
}
find(value) {
//accepts an integer value and search for it in the tree. IF found ,return the node with the value;
if (this.root === null) {
return undefined;
}
let current = this.root;
while (current) {
if (current.value === value) {
return current;
} else if (current.value > value) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
levelOrder(callback) {
//BFS
const queue = [];
const data = [];
let node = this.root;
queue.push(this.root);
while (queue.length) {
node = queue.shift();
data.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return data;
}
inOrder(callback) {
//inOrderDFS
if (this.root === null) {
return undefined;
}
const data = [];
let current = this.root;
const traverse = (node) => {
if (node.left) {
traverse(node.left);
}
data.push(node.value);
if (node.right) {
traverse(node.right);
}
};
traverse(current);
return data;
}
preOrder(callback) {
//preOrderDFS
if (this.root === null) {
return undefined;
}
const data = [];
let current = this.root;
const traverse = (node) => {
data.push(node.value);
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
};
traverse(current);
return data;
}
postOrder(callback) {
//postOrderDFS
if (this.root === null) {
return undefined;
}
const data = [];
let current = this.root;
const traverse = (node) => {
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
data.push(node.value);
};
traverse(current);
return data;
}
}
const odinTree = new BinarySearchTree();
const array = [10, 20, 12, 15, 11, 50, 35, 21, 5, 2, 9, 3];
odinTree.buildTree(array);
Here’s the code for deleteNode:
deleteNode(value) {
let current = this.root;
let prev;
if (!current) {
console.log("hello");
return undefined;
}
while (current) {
if (current.value > value) {
prev = current;
current = current.left;
} else if (current.value < value) {
prev = current;
current = current.right;
} else {
//node found.
//case 1: node is leaf node, no left and right children
if (!current.left && !current.right) {
if (prev.value > current.value) {
prev.left = null;
} else {
prev.right = null;
}
console.log("leaf node deleted", current);
return this;
}
//case 2: node has either left or right child
//case 3: node has both left and right children
}
}
}
I tried running the code on console, and it actually worked. However, I tried refreshing the page and I pressed keyup to run the same code to delete the same leaf node and it got stuck.
I’m quite sure my code is fine because i tried typing out tree.deleteNode on several leaf nodes and they all worked. The page only got stuck whenever i tried running deleteNode by pressing keyup.
Any inputs would be appreciated, thank you!
