Tree.js

gistfile1.txt

// data structure for node
var Node = function(char,isLastChar){
	this.char = char;
	this.isLastChar = isLastChar;
	this.children = {};	
};
//adds a word to a node/tree
var addWord = function(tree,word){
	var chars = word.split('');
	//when adding a node to a tree, the currentNode starts as the tree
	var currentNode = tree;
	for(var i = 0;i < chars.length; i ++){
		//if the current char is not in the tree then add it
		if(!currentNode.children[chars[i]]){
			var newNode = new Node(chars[i],i == (chars.length -1));
			currentNode.children[newNode.char] = newNode;	
			//each node only needs to know about its children, so set the current node to newly inserted node
			currentNode = newNode;
		} else {
			//if we already have the node just set the node to the current node
			currentNode = currentNode.children[chars[i]];
		}
	}
};
var printWords = function(tree,currentChars,depth){
	for(var child in tree.children){
		//if the node is the last character of a word print it
		if(tree.children[child].isLastChar) {
			console.log('Depth: '+depth + currentChars + child);
		} 
		//if there is more children then recurse with the current chars + the current nodes char
		if(Object.keys(tree.children[child].children).length) {
			printWords(tree.children[child],currentChars+child,depth+1);	
		}
	}
};
var tree = new Node('',false);
addWord(tree,'all');
addWord(tree,'allot');
addWord(tree,'alloy');
addWord(tree,'aloe');
addWord(tree,'cab');
addWord(tree,'car');
addWord(tree,'cat');
addWord(tree,'catch');
addWord(tree,'caught');
addWord(tree,'caring');
//printWords(tree,'',0);
for(var i = 0; i < 10000000; i++){
	addWord(tree,i.toString());
}
console.log('done');