Two ways to visit every node

Depth-first goes all the way down one branch before the next, and recursion does it for free. Breadth-first goes level by level, and needs a queue.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

The choice changes the answer, not only the speed: breadth-first reaches a node by a shortest route, depth-first by whichever route it wandered down first.

How to think about it

Say the requirement out loud. 'In order', 'sum down a path', 'all of this branch': depth-first, write it recursively. 'Level by level', 'nearest first': breadth-first, use a queue.

Worked example

const node = (value, left = null, right = null) => ({ value, left, right });

const root = node(5, node(3, node(1), node(4)), node(8, node(7)));

const inorder = n => (n === null ? [] : [...inorder(n.left), n.value, ...inorder(n.right)]);

Left, self, right: the order of the three pieces IS the walk.

console.log(inorder(root).join(','));

1,3,4,5,7,8

const out = [], queue = [root];

Everything still to visit.

let head = 0;

The front of the queue.

while (head < queue.length) {

  const n = queue[head++];

The shallowest node still waiting.

  if (n === null) continue;

  out.push(n.value);

  queue.push(n.left, n.right);

Children go to the BACK, so they wait their turn.

console.log(out.join(','));

5,3,8,1,4,7

Your turn

Make the walk breadth-first rather than depth-first.

const next = queue[];
queue.push(next.left, next.right);

The trap

Take from the back of that array instead of the front and the same loop silently becomes depth-first. Same code, different answer, no error.

Practise walking a tree on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.