Skip to content

Instantly share code, notes, and snippets.

@nhnam
Created January 3, 2022 13:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nhnam/7c57e838c3ce08b57ff4b4d2a245ebfd to your computer and use it in GitHub Desktop.
Save nhnam/7c57e838c3ce08b57ff4b4d2a245ebfd to your computer and use it in GitHub Desktop.
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
this.parent = null;
}
function BSTree() {
this.root = null;
}
BSTree.prototype.insert = function (key) {
if (this.root === null) {
this.root = new Node(key);
return;
}
this.insertChild(key, this.root);
};
BSTree.prototype.insertChild = function (key, node) {
// find the spot to insert
if(node.key > key) {
if(node.left === null) {
node.left = new Node(key);
node.left.parent = node;
return;
} else {
this.insertChild(key, node.left);
}
} else {
if(node.right === null) {
node.right = new Node(key);
node.right.parent = node;
return;
} else {
this.insertChild(key, node.right);
}
}
}
BSTree.prototype.build = function (keys, node) {
for (var i = 0; i < keys.length; i++) {
this.insert(keys[i], this.root);
}
};
BSTree.prototype.contains = function (key, anode, path) {
var node = anode ? anode : this.root;
if (!node) {
return false;
}
if (node.key === key) {
path.push(node.key); // found
return true;
}
if (node.left === null && node.right === null) {
path.push('not found');
return false;
}
path.push(node.key);
if (node.key > key) {
return this.contains(key, node.left, path);
} else {
return this.contains(key, node.right, path);
}
};
let aTree = new BSTree();
aTree.build([5, 6, 8, 3, 7, 9, 10]);
var path = [];
// aTree.contains(11, null, path); // 5,6,8,9,not found
aTree.contains(8, null, path); // 5,6,8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment