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.)

On the surface at least, this is a duplicate of [*What is the scope of variables in JavaScript?*](https://stackoverflow.com/questions/500431/), but I don't want to use my dupehammer, I'm really not sure that's sufficient explanation. — T.J. Crowder, Apr 12 '23 at 11:58
[`typeof` operator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/typeof) returns the type of the variable/value. — Nina Scholz, Apr 12 '23 at 12:01

score 1 · Answer 1 · answered Apr 12 '23 at 11:58

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.

score 1 · Accepted Answer · answered Apr 12 '23 at 11:58

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)

score 0 · Answer 3 · answered Apr 12 '23 at 11:58

0

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

if (!typeof ancestors){

defining before this line will solve the issue

answered Apr 12 '23 at 11:58

Packiyaraj Patchath

74
4

Javascript Tree (Array of object) Traversal with Ancestors

3 Answers3