html
You've reached the depths of our data structure, where the trees are treacherous and the graphs are gnarly.
A tree with a bad haircut, the BST is the most common choice for beginners. It's like a big ol' mess of nodes, but hey, it's easy to implement.
// Binary Search Tree
//
// Create a new node
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
// Insert a value into the tree
function insert(value) {
if (!this.root) {
this.root = new Node(value);
} else {
this.insertNode(this.root, value);
}
}
// Traverse the tree in-order
function inOrder(node) {
if (node) {
inOrder(node.left);
process.stdout.write(node.value);
inOrder(node.right);
}
}
//
Learn more about BST basics
A tree with a penchant for prefixes, the Trie is like a big ol' party with all your favorite words. Except, you know, it's a data structure.
// Trie
//
// Create a new node
function Node(word) {
this.value = word;
this.children = {};
}
// Insert a word into the trie
function insert(word) {
var currentNode = this.root;
for (var i = 0; i < word.length; i++) {
if (!currentNode.children[word[i]]) {
currentNode.children[word[i]] = new Node(word);
}
currentNode = currentNode.children[word[i]];
}
}
// Check if a word exists in the trie
function exists(word) {
var currentNode = this.root;
for (var i = 0; i < word.length; i++) {
if (!currentNode.children[word[i]]) {
return false;
}
currentNode = currentNode.children[word[i]];
}
return true;
}
//
Learn more about Tries in action
But wait, what about graph traversal?