How to traverse a General Tree (not BST) recursively in JavaScript?

Question

Let's say that we want to model de hierarchical structure present in a company. The most basic data structure is called employee. Each employee is an Object / Tree of it's own and has two attributes: level which is an integer and reports that is an Object / Tree holding 0 or more employees.

We could say that the employee data structure looks as follows:

{
    employee: {
        level: Number,
        reports: Object //Contains 0 to N employees
    }
}

A small business could represent it's organization as follows:

{
boss: {
  level: 0,
  reports: {
    employee0: {
      level: 1,
      reports: {
        anotherEmployee0: {
          level: 2,
          reports: { /* ... */ },
        },
        anotherEmployee0: {
          level: 2,
          reports: { /* ... */ },
        },
      },
    },
    employee1: {
      level: 1,
      reports: { /* ... */ },
    },
  },
},
};

How can we traverse this structure using recursion? Ideally, doing it without language function abstractions such as for ... in, foreach, map. So, 'by hand'. I'd love to see both solutions (with and without said abstractions), to compare.

Answer 1

Trincot's excellent answer used generators "instead of the old-fashioned callback system".

Here's a demonstration of how that old-fashioned system might work, using trincot's restructuring of the input data:

const traverseOrg = (fn) => (org, boss = null) =>
  org .forEach (emp => {
    fn (emp, boss)
    traverseOrg (fn) (emp.reports || [], emp) 
  })

let org2 = [{name: "boss", level: 0, reports: [{name: "employee0", level: 1, reports: [{name: "anotherEmployee0", level: 2, reports: [/* ... */]}, {name: "anotherEmployee1", level: 2, reports: [/* ... */]}]}, {name: "employee1", level: 1, reports: [/* ... */]}]}];

traverseOrg (
  ({level, name}, boss) => console .log (
    `${'    ' .repeat (level)}${name} (level ${level}) reports to ${boss ? boss.name : "no one"}`
  )
) (org2)

Our traverseOrg function takes a callback function and generates a function that takes an array of employees with their nested reports, and calls the callback on each one in a depth-first traversal, passing the employee and the parent employee, or null if it doesn't exist.

We can use this for the same sort of output that trincot demonstrated, by simply logging the employee name, level, and boss' name.

Note that we use forEach here. We could many types of looping construct, but since we're treating this as a simple traversal, and not a transformation, the array functions such as .map or .reduce are not appropriate here.

We could layer out a flattening function on top of this, with something like this:

const flattenOrg = (org) => {
  const res = []
  traverseOrg (({name, reports = []}) => res .push (
    {name, directReports: reports .map (({name}) => name)}
  )) (org)
  return res
}

flattenOrg (org2)

which would return this structure:

[
  {name: "boss", directReports: ["employee0", "employee1"]},
  {name: "employee0", directReports: ["anotherEmployee0", "anotherEmployee1"]},
  {name: "anotherEmployee0", directReports: []},
  {name: "anotherEmployee1", directReports: []},
  {name: "employee1", directReports: []}
]

But there's not much reason for that. It's ugly code, and we would do better to write it directly:

const flattenOrg = (org) =>
  org .flatMap (({name, reports = []}) => 
    [{name, directReports: reports .map (({name}) => name)}, ... flattenOrg (reports)]
  )

Answer 2

for..in is a core language construct that has been part of the JavaScript language from its inception. It is the first way that was provided to inspect the properties of an object.

I provide here two solutions. The first one will stick to your data structure, and will employ for..in to read the properties of the given objects and perform conditional recursion on the reports value. It calls a user-provided callback function, so the user can decide what to do with the iterated values.

The second one switches to a better data structure, as it is better practice to not use object property names to represent dynamic content. Instead add a property to your objects (maybe "name") to which you assign that dynamic content ("employee1", "boss", ...etc). Instead of the old-fashioned callback system, it defines the function as a generator.

Solution 1 (for..in + callback):

This is ES3 compatible.

function traverse(org, callback, parent) {
    for (var name in org) {
        var obj = org[name];
        callback(name, obj.level, parent);
        if (obj.reports) {
            traverse(obj.reports, callback, name);
        }
    }
}

// demo with original data structure
var org = {boss: {level: 0,reports: {employee0: {level: 1,reports: {anotherEmployee0: {level: 2,reports: { /* ... */ },},anotherEmployee1: {level: 2,reports: { /* ... */ },},},},employee1: {level: 1,reports: { /* ... */ },},},},};

traverse(org, visit, null);

// Our function that processes the iterated values:
function visit(name, level, parent) {
    console.log("         ".slice(0, level) + name + " (level " + level + ") under " + (parent || "no one"));
}

Solution 2: (better data structure + generator)

This also uses destructuring, for..of loop, template literal, repeat, let, default argument value, ...

function * iterate(org, parent=null) {
    for (let {name, level, reports} of org) {
        yield [name, level, parent];
        if (reports) {
            yield * iterate(reports, name);
        }
    }
}

let org2 = [{ 
    name: "boss", 
    level: 0, 
    reports: [{ 
        name: "employee0", 
        level: 1, 
        reports: [{ 
            name: "anotherEmployee0", 
            level: 2, 
            reports: [/* ... */]
        }, { 
            name: "anotherEmployee1", 
            level: 2, 
            reports: [/* ... */]
        }]
    }, {
        name: "employee1",
        level: 1,
        reports: [/* ... */]
    }]
}];

for (let [name, level, parent] of iterate(org2)) {
    console.log(`${" ".repeat(level)}${name} (level ${level}) under ${parent || "no one"}`);
}