Tree: Breadth-first and Depth-first

A tree is a data structure with nodes. There are many different types of trees but all trees use collection of nodes to store data. Let's create a Node and Tree class and traverse the tree breadth-first and depth-first.

Node

A node has two properties: data and children of nodes.

class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
}

Tree

A tree has reference to a root node.

class Tree {
  constructor() {
    this.root = null;
  }
}

Traversal

The starting point is always the same, but there are many ways to traverse the tree from the same starting point.

Breadth-first

Breadth-first traversal goes through each level. It will not move on to the next level unless everyone in the current level has been visited.

1. Put root of the tree in an array.
2. While there are elements in this array, take out the very first element and PUSH all of its children into the back of the array.

class Tree {
  // ...

  traverseBreadthFirst(lambda) {
    if (!this.root) {
      return;
    }

    const nodeArray = [this.root];

    while (nodeArray.length) {
      const firstElement = nodeArray.shift();

      lambda(firstElement);

      nodeArr.push(...firstElement.children)
    }
  }
}

Depth-first

Depth-first traverses into a deeper level if possible until it can go no longer. Once it cannot go any deeper, it backtraces to the last parent node in which all of its children have not been explored yet.

1. Put the root of the tree in an array.
2. While there are elements in this array, take out the very first element and UNSHIFT all of its children into the front of the array.

class Tree {
  // ...

  traverseDepthFirst(lambda) {
    if (!this.root) {
      return;
    }

    const nodeArray = [this.root];

    while (nodeArray.length) {
      const firstElement = nodeArray.shift();

      lambda(firstElement);

      nodeArr.unshift(...firstElement.children);
    }
  }
}