BST
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
class Node {
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value)
if (this.root === null) {
this.root = newNode
} else {
let currentNode = this.root
while (true) {
if (value < currentNode.value) {
if (!currentNode.left) {
currentNode.left = newNode
return this
}
currentNode = currentNode.left
} else {
if (!currentNode.right) {
currentNode.right = newNode
return this
}
currentNode = currentNode.right
}
}
}
}
lookup(value) {
if (!this.root) {
return false
}
let currentNode = this.root
while(currentNode) {
if (value < currentNode.value) {
currentNode = currentNode.left
} else if (value > currentNode.value) {
currentNode = currentNode.right
} else if (value === currentNode.value) {
return currentNode
}
}
return false
}
remove(value) {
}
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
//tree.remove(170);
console.log(JSON.stringify(traverse(tree.root)));
console.log(tree.lookup(4));
// 9
// 4 20
//1 6 15 170
function traverse(node) {
const tree = { value: node.value };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
JavaScript
INFO