DEV Community

Snir David
Snir David

Posted on

Breadth first traversal for binary trees in JS

Breath first traversal of binary trees is a basic thing to do.
So why do I write this post?
Because there is a gap if you try to quickly look for implementation in google.

Most of the articles cover generic trees, not binary tress. Thus have no concept of "left" and "right" nodes, but just unordered children.
https://medium.com/@kenny.hom27/breadth-first-vs-depth-first-tree-traversal-in-javascript-48df2ebfc6d1
https://medium.com/@stephaniewo/understanding-breadth-first-tree-traversal-with-javascript-9b8fe670176d
https://gist.github.com/thinkphp/1440007

And this might confuse a beginner.
Others, like this great article at hackernoon do a perfect job explaining the concept, but not presenting the code for it.

bft-tree
gif by by Stephanie Wong

So, assuming you'll read the concept of how we use queues to do the breadth first traversal at this great article at hackernoon, here is a modern implementation, specific to binary trees with left and right nodes.
(And as in the gif above, it will always go from left to right)

class Tree {
  constructor(value, left, right) {
    this.value = value
    this.left = left
    this.right = right
  }
}

const breadthFirstTraversal = (tree, callback) => {
  if (tree == null) {
    return;
  }

  let queue = [tree]

  while (queue.length > 0) {
    let item = queue.shift()
    let value = item.value
    callback(value)

    if (item.left == null && item.right == null) {
      continue
    }
    if (item.left != null) {
      queue.push(item.left)
    }
    if (item.right != null) {
      queue.push(item.right)
    }
  }
}

t = new Tree(1,
      new Tree(2, null, null), new Tree(3,
        new Tree(4, null, null), null))

breadthFirstTraversal(t, console.log)
// Will print "1,2,3,4"

Top comments (2)

Collapse
 
ggenya132 profile image
Eugene Vedensky • Edited

Finally a practical example of breadth first traversal that's fairly straight-forward to read. Thank you!

EDIT: Now, can we have an example of depth first in JS?

Collapse
 
snird profile image
Snir David

I'll get on it (: