naive dfs

naive-dfs.js

function dfs (vertex, visited) {
  if (visited.indexOf(vertex.id) !== -1) { // cut visited nodes
    return null
  }
  if (!vertex.children) { // leaf, return its value
    return { id: vertex.id, sum: vertex.value }
  } else { // inner node, traverse leaves and aggregate their values
    var sum = 0
    var childSums = []
    for (var child in vertex.children) {
      console.log(vertex.children[child])
      var _visited = visited.slice() // we need a copy of this for every branch
      _visited.push(vertex.id)
      var childSum = dfs(vertex.children[child], _visited)
      console.log(childSum)
      if (childSum) {
        sum += childSum.sum
        childSums.push(childSum)
      }
    }
    return {id: vertex.id, sum: sum, children: childSums}
  }
}

var a = {
  id: 'a',
  value: 2
}

var c = {
  id: 'c',
  value: 3
}

var b = {
  id: 'b',
  children: [c]
}

b.children.push(b) // add circle

var r = {
  id: 'r',
  children: [a, b]
}

console.log(dfs(r, []))