Skip to content

Instantly share code, notes, and snippets.

@ben8p
Created July 4, 2016 07:24
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 ben8p/deedf1f8f4e1f52a1ab7fdec6615c3cb to your computer and use it in GitHub Desktop.
Save ben8p/deedf1f8f4e1f52a1ab7fdec6615c3cb to your computer and use it in GitHub Desktop.
Binary tree in JS (Breadth first search, insort, insert)
/** recursively search in the tree where the current value can be inserted */
function find(value, node) {
if(node.value === undefined || node.value === value) {
return node;
}
if(node.value > value) {
return find(value, node.left);
}
return find(value, node.right);
}
/** traverse the tree with insort method */
function inSort(node) {
var value = [];
if(node.left) {
value = value.concat(inSort(node.left));
}
if(node.value !== undefined) {
value = value.concat([node]);
}
if(node.right) {
value = value.concat(inSort(node.right));
}
return value;
}
/* create a tree from an array of values */
function createTree(values, rootIndex) {
var root = {
left: {},
right: {},
value: values[rootIndex]
};
values.forEach(function(value) {
var node = find(value, root);
if(value === node.value) { return; }
node.value = value;
node.left = {};
node.right = {};
});
return root;
}
/* breadth first search */
function BFS(tree) {
var levels = [];
function traverse(root, level) {
level = level || 0;
levels[level] = levels[level] || [];
var nextLevel = level + 1;
if(root.left) {
traverse(root.left, nextLevel);
}
if(root.value) {
if(!levels[level]) { debugger; }
levels[level].push(root.value);
}
if(root.right) {
traverse(root.right, nextLevel);
}
return levels;
}
return traverse(tree).join("\n");
}
//values to put in the tree
var values = [88,97,56,41,27,16,95,54,28];
//create tree
var tree = createTree(values, 0);
console.log('tree:', tree);
//insort tree traversing
var sorted = inSort(tree);
console.log('sorted:', sorted);
//recreate tree with median as starting point
var median = sorted[Math.round(sorted.length / 2)].value;
var treeMedian = createTree(values, values.indexOf(median));
console.log('tree median (', median, '):', treeMedian);
//Breadth first search
console.log(BFS(treeMedian));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment