Depth First Search (Trees)

Depth First Search was previously covered in my blog here but as I’ve been exploring more programmatic “use cases” with my other Code Pattern posts, I get the impression that Depth First Search could be useful in programming some “Natural Language Processor” to check for specific meaning first and then back up to something more general.

In the code example that follows below, I treat each node as a letter… but thinking about this in the context of “Natural Language Processing” or “Processing for Meaning” I suspect you’d want to FizzBuzz for the most in depth example before backtracking to something more generic. NOTE: by “FizzBuzz” I mean checking for the total “combination/sequence” prior to checking for any specific parts.

Perhaps a “root node” expresses joy. The left node is “genuine joy” and the right node is joy of the “schadenfreude” variety. The left.left node is genuine joy for something accomplished by the individual, the left.right node is genuine joy for something accomplished by someone else. The right.left node is schadenfreude related to recognition of some past suffering/enjoyment to see someone else suffering as “you” have, whereas the right.right node is more overtly malicious schadenfreude — simple enjoyment of another’s misfortune.

If your program needed to traverse this tree to come up with some sort of specific response, it would make sense for it to match by depth/specificity as that would make it possible to respond “quicker” as opposed to going level by level. Especially if the tree wasn’t just 3 levels, but 3000.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function hasWord(root, word) {
  if (root === null) {
    return word.length === 0;
  }

  return find_word_recursively(root, word, 0);
}


function find_word_recursively(currentNode, word, wordIndex) {
  if (currentNode === null) {
    return false;
  }

  let wordLength = word.length;
  // check to see if the wordIndex is greater than or equal to the word length
  // OR... if the currentNode value is NOT equal to "whatever" value of the word is at "whatever" index
  if (wordIndex >= wordLength || currentNode.val !== word[wordIndex]) {
    return false;
  }

  if (currentNode.left === null && currentNode.right === null && wordIndex === wordLength - 1) {
    return true;
  }

  return find_word_recursively(currentNode.left, word, wordIndex + 1) ||
    find_word_recursively(currentNode.right, word, wordIndex + 1);
}


const root = new TreeNode("c");
root.left = new TreeNode("a");
root.right = new TreeNode("o");
root.left.left = new TreeNode("t");
root.left.right = new TreeNode("r")
root.right.left = new TreeNode("n");
root.right.right = new TreeNode("d");
console.log(`Tree has path: ${hasWord(root, "cat")}`);
console.log(`Tree has path: ${hasWord(root, "con")}`);
console.log(`Tree has path: ${hasWord(root, "cor")}`);

Cast of Characters:
– Classroom
– Construction Workers
– Wart Nosed Lewis and Clark
– Rabbi with a Cigar Cutter
– Rabbi with Super Glue
– Supporting Cast & Crew
– Cobb from Inception (3 levels of control flow for the recursive function)

Glossary of Code Personified

Return to the Pattern Directory