Skip to content

Instantly share code, notes, and snippets.

@vinothbabu
Last active December 17, 2015 00:11
Show Gist options
  • Save vinothbabu/5519325 to your computer and use it in GitHub Desktop.
Save vinothbabu/5519325 to your computer and use it in GitHub Desktop.
BinarySearchTree
function BinarySearchTree() {
this._root = null;
}
BinarySearchTree.prototype = {
constructor: BinarySearchTree,
add: function (value) {
var node = {
value: value,
left: null,
right: null,
},
current;
if (this._root === null) {
this._root = node;
} else {
current = this._root;
while (true) {
if (value < current.value) {
if (current.left === null) {
current.left = node;
break;
} else {
current = current.left;
}
} else if (value > current.value) {
if (current.right === null) {
current.right = node;
break;
} else {
current = current.right;
}
} else {
break;
}
}
}
},
contains: function (value) {
var found = false,
current = this._root;
while (!found && current) {
if (value < current.value) {
current = current.left;
} else if (value > current.value) {
current = current.right;
} else {
found = true;
}
}
return found;
},
remove: function (value) {
},
size: function (value) {
var len = 0;
function length(node) {
if (node) {
if (node.left != null) {
length(node.left);
}
len++;
if (node.right != null) {
length(node.right);
}
}
}
length(this._root);
return len;
},
toArray: function (value) {
var results = [];
function length(node) {
if (node) {
if (node.left != null) {
length(node.left);
}
results.push(node.value);
if (node.right != null) {
length(node.right);
}
}
}
length(this._root);
return results;
},
toString: function () {
return this.toArray().toString();
}
}
<!DOCTYPE html>
<html>
<head>
<meta charset=utf-8 />
<title>JS Bin</title>
<script type="text/javascript" src="BinarySearchTree.js"></script>
</head>
<body>
<script TYPE="text/javascript">
var tree = new BinarySearchTree();
tree.add(5);
tree.add(15);
tree.add(25);
document.write(tree.contains(5));
document.write(tree.contains(15));
document.write(tree.contains(45));
document.write(tree.size());
document.write(tree.toArray());
document.write(tree.toString());
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment