Skip to content

Instantly share code, notes, and snippets.

@fundon
Created August 25, 2011 09:29
Show Gist options
  • Select an option

  • Save fundon/1170314 to your computer and use it in GitHub Desktop.

Select an option

Save fundon/1170314 to your computer and use it in GitHub Desktop.
Binary tree in JavaScript
function cons(x, y) {
return function(w) { return w(x, y) };
};
function car(z) {
return z(function(x, y) { return x });
};
function cdr(z) {
return z(function(x, y) { return y });
};
function make_tree(entry, left, right) {
return cons(entry, cons(left, cons(right, null)));
}
function entry(tree) {
return car(tree);
}
function left_branch(tree) {
return car(cdr(tree));
}
function right_branch(tree) {
return car(cdr(cdr(tree)));
}
/** assumes binary search tree **/
function element_of_set(value, tree) {
if (!tree) return false;
var current = entry(tree);
if (current == value) return true;
if (current > value) return element_of_set(value, left_branch(tree));
return element_of_set(value, right_branch(tree));
}
/** make a simple binary search tree **/
var tree = make_tree(4,
make_tree(2,
make_tree(1, null, null),
make_tree(3, null, null)),
make_tree(6,
make_tree(5, null, null),
make_tree(7, null, null)));
document.writeln(element_of_set(7, tree));
document.writeln(element_of_set(3.5, tree));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment