Skip to content

Instantly share code, notes, and snippets.

@maurobaraldi
Created December 16, 2014 03:06
Show Gist options
  • Save maurobaraldi/262cb79d6074293bbff0 to your computer and use it in GitHub Desktop.
Save maurobaraldi/262cb79d6074293bbff0 to your computer and use it in GitHub Desktop.
Count elements in a binary search tree
// add an element to a tree
var add_elem = function(tree, value) {
if(tree === null) {
return {
data: value,
left: null,
right: null
};
}
if(value <= tree.data) {
return {
data: tree.data,
left: add_elem(tree.left, value),
right: tree.right
};
} else {
return {
data: tree.data,
left: tree.left,
right: add_elem(tree.right, value)
};
}
};
// create a tree from a list of elements
var create_tree = function(lst) {
var i;
var curr = null;
for(i = 0; i < lst.length; i++) {
curr = add_elem(curr, lst[i]);
}
return curr;
};
// count binary search tree recursively
var count = function(tree) {
counter = 0;
if (tree === null){
return counter;
}
if (tree.left !== null || tree.right !== null){
counter++;
}
return 1 + count(tree.left) + count(tree.right);
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment