html

Data Structure Traversal

You've reached the depths of our data structure, where the trees are treacherous and the graphs are gnarly.

Binary Search Tree (BST)

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

Trie (prefix tree)

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?