Walk a menu tree breadth-first and depth-first

A navigation menu, a comment thread or a file tree can be walked two ways. Breadth-first visits everything on one level before descending, which is what you want when rendering a menu level by level or finding the nearest match. Depth-first follows one branch to the bottom first, which is what you want when flattening for display.

Implement two functions over the same node shape { id, children }, where children is an array of nodes and may be missing. Both take roots, an array of top-level nodes, and both return an array of id values; both return [] for an empty array of roots.

breadthFirst(roots) returns ids level by level: every root in array order first, then every child of those roots in the same order their parents were visited, then every grandchild, and so on. depthFirst(roots) returns ids in pre-order: each node immediately before its own descendants, with siblings in array order.

What it has to do

• breadthFirst visits all nodes at one level before any node at the next.
• depthFirst visits a node immediately before its descendants.
• Both keep siblings in their array order.
• Both return an empty array when given no roots.
• Both treat a missing children property as no children.

Your workspace