Javascript Tree (Array of object) Traversal with Ancestors

Question

I am trying to make a tree traversal function in javascript. I also want ancestors of any nodes. That's why I have written code like this:

const visit = (tree) => {
  if (!typeof ancestors){
    const ancestors = []
  }
  console.log(ancestors)
  if (Array.isArray(tree.children)) {
    ancestors.push(tree)
    tree.children.forEach((e) => {
      visit(e);
    })
  }
}

visit({
   "type":"root",
   "children":[
      {
         "type":"element",
         "children":[
            {
               "type":"element"
            },
            {
               "type":"element"
            },
            {
               "type":"element"
            },
            {
               "type":"element"
            }
         ]
      },
      {
         "type":"element"
      },
      {
         "type":"element"
      },
      {
         "type":"element"
      }
   ]
})

But it is giving me error:

Error: ancestors is not defined

Can someone help me what to do? (I don't want to put this ancestors as property of object.)

Answer 1

const variables are block-scoped

You can create a wrapper function if you don't want to have a global variable

const visit = (tree) => {
  const ancestors = []
  const req = (tree) => {
    if (Array.isArray(tree.children)) {
      ancestors.push(tree)
      tree.children.forEach((e) => {
        req(e);
      })
    }
  }
  
  req(tree)

  return ancestors
}

const result = visit({
  "type": "root",
  "children": [{
      "type": "element",
      "children": [{
          "type": "element"
        },
        {
          "type": "element"
        },
        {
          "type": "element"
        },
        {
          "type": "element"
        }
      ]
    },
    {
      "type": "element"
    },
    {
      "type": "element"
    },
    {
      "type": "element"
    }
  ]
})

console.log(result)

Answer 2

As ancestors is defined after this line, so the error occurs

if (!typeof ancestors){

defining before this line will solve the issue

Answer 3

The shortest solution is to make ancestors an argument with a default value and to pass ancestors to subsequent recursive calls:

const visit = (tree, ancestors = []) => {
  console.log(ancestors)
  if (Array.isArray(tree.children)) {
    ancestors.push(tree)
    tree.children.forEach((e) => {
      visit(e, ancestors);
    })
  }
}

if you then call visit(tree), ancestors will implicitly be initialized to [].

Alternatives would be to use a closure as in Konrad's answer or to switch to an entirely iterative implementation, manually managing the stack.