Breadth First Search (Trees)

For a better explanation of Breadth First Search, check out my previous algonalogy for Breadth First Search. For the example here, we’ll be going level by level and returning the averages for each level.

class SomeTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function traverse_and_average_level(root) {
  result = [];
  if (root === null) {
    return result;
  }

  const level = [];
  level.push(root);
  while (level.length > 0) {
    let levelSize = level.length,
      levelSum = 0.0;
    for (i = 0; i < levelSize; i++) {
      currentNode = level.shift();
      levelSum += currentNode.value;
      if (currentNode.left !== null) {
        level.push(currentNode.left);
      }
      if (currentNode.right !== null) {
        level.push(currentNode.right);
      }
    }
    result.push(levelSum / levelSize);
  }

  return result;
}


// for convenience level 1 starts with 1, level 2 with 2 and level 3 with 3... in other words level 31 is level 3. You'll also notice that odds represent a left (or original) value, and evens represent a right value.
const root = new SomeTreeNode(11);
root.left = new SomeTreeNode(21);
root.right = new SomeTreeNode(22);
root.left.left = new SomeTreeNode(31);
root.left.right = new SomeTreeNode(32);
root.right.left = new SomeTreeNode(33);
root.right.right = new SomeTreeNode(34);
console.log(`Averages for each level ${traverse_and_average_level(root)}`);]

Cast of Characters:
-Wart Nose Climbing a Tree
-Construction Workers
-Lewis and Clark
-Retired Turtle Bouncer
-Wile E. Coyote
-Forex Trader
-Pushy Car Salesman
-Shifty Eyed Shoplifter

Glossary of Code Personified

Return to the Pattern Directory