This is probably something really stupid but I cannot figure out why in the removal function when it’s called the node isn’t being mutated.
class TreeNode {
key: number;
value: string;
left: TreeNode;
right: TreeNode;
parent: TreeNode;
// Key ID; Value: any;
constructor(key: number, value: any) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
}
}
export default TreeNode;
import TreeNode from './TreeNode.js';
const ErrorDuplicateKey = new Error("duplicate key")
const ErrorKeyNoExist = new Error("key doesn't exist")
const ErrorNoRoot = new Error("no root")
// Right >
// Left <
class Tree {
root: TreeNode;
_count: number;
constructor() {
this.root = null;
this._count = 0;
}
count(): number {
return this._count;
}
min(startingNode: TreeNode = this.root): TreeNode {
if(!this.root) {
return null;
}
let current = this.root;
while(current) {
if(current.left == null) {
return current;
}
current = current.left;
}
}
max(): TreeNode {
if(!this.root) {
return null;
}
let current = this.root;
while(current) {
if(current.right == null) {
return current
}
current = current.right;
}
}
insert(newKey: number, newValue: string) {
this._count++;
const newNode = new TreeNode(newKey, newValue)
// If the root is nil set the root
if(!this.root) {
this.root = newNode;
return this.root;
}
let current = this.root;
while(current) {
if(newKey === current.key) {
return ErrorDuplicateKey;
}
if(newKey > current.key) {
if(current.right === null) {
current.right = newNode;
return this;
}
current = current.right
continue
}
if(newKey < current.key) {
if(current.left === null) {
current.left = newNode;
return this;
}
current = current.left
}
}
}
find(key: number): TreeNode {
if(!this.root) {
return null
}
let current = this.root;
while(current) {
if(current.key == key) {
return current
}
if(key > current.key) {
current = current.right
continue;
}
if (key < current.key) {
current = current.left
}
}
return null;
}
remove(key: number): Tree {
if (!this.root) {
return null;
}
let current = this.root;
while(current) {
// is leaf
if(key === current.key) {
if(current.right && current.left) {
console.log("right and left")
current = this.min(current.right)
continue;
}
if (!current.left && !current.right) {
console.log("is leaf")
current = null;
return this;
}
if(current.left === null) {
console.log("left is null")
current = current.right;
return this;
}
if(current.right === null) {
console.log("right is null")
current = current.left;
return this;
}
}
if(key < current.key) {
current = current.left;
}
if(key > current.key) {
current = current.right;
}
}
}
dfsInOrder(): Array<number> {
let nodesToVisit = [this.root];
let visitedNodes = [];
while(nodesToVisit.length > 0) {
let current = nodesToVisit.pop()
visitedNodes.push(current.key)
if(current.left) {
nodesToVisit.push(current.left)
}
if(current.right) {
nodesToVisit.push(current.right)
}
}
return visitedNodes;
}
isValidTree(): boolean {
// Traverse Left
let isValidLeft = true;
let currentLeft = this.root;
while(currentLeft) {
if(currentLeft.left === null) {
break;
}
if(currentLeft.left !== null) {
// If the current node is less than the child node
// Then we know that the tree is not valid because the child node
// should be greater than the current node because we're going right
if(currentLeft.key < currentLeft.left.key) {
isValidLeft = false;
}
currentLeft = currentLeft.left;
}
}
// Traverse Right
let isValidRight = true;
let currentRight = this.root;
while(currentRight) {
if(currentRight.right === null) {
break;
}
if(currentRight.right !== null) {
// If the current node is greater than the child node
// Then we know that the tree is not valid because the child node
// should be greater than the current node because we're going right
if(currentRight.key > currentRight.right.key) {
isValidRight = false;
}
currentRight = currentRight.right;
}
}
return isValidLeft && isValidRight;
}
}
export default Tree;
let bst = new BinarySearchTree();
bst.insert(9, "nine");
bst.insert(4, "four");
bst.insert(6, "six");
bst.insert(20, "twenty");
bst.insert(170, "one hundred seventy");
bst.insert(15, "fifteen");
bst.insert(1, "one");
bst.insert(2, "two");
bst.insert(3, "three");
bst.insert(5, "five");
bst.insert(7, "seven");
bst.insert(8, "eight");
bst.insert(10, "ten");
bst.insert(11, "eleven");
bst.insert(12, "twelve");
bst.insert(13, "thirteen");
bst.insert(14, "fourteen");
bst.insert(16, "sixteen");
bst.insert(17, "seventeen");
bst.remove(10);
console.log(bst.dfsInOrder())
/*[
9, 20, 170, 15, 16, 17, 10,
11, 12, 13, 14, 4, 6, 7,
8, 5, 1, 2, 3
]*/
console.log(bst.isValidTree())