Trying to extract items from a nested javascript object tree using recursion

Question

I'm trying to learn recursion and I have a code that tries to extract all parent names and push them to array if they have children.

My problem is that I am able to print out all the parents but can only seem to push 2 out of 5 of them.

function printChildrenRecursive(t) {
  let hasChildren = []

  if (t.children.length === 0) {
    return
  }

  t.children.forEach(child => {
    if (child.children.length > 0) {
      console.log(child.name)
      hasChildren.push(child.name)
    }
    printChildrenRecursive(child)
  })

  return hasChildren
}

const tree = {
  name: 'John',
  children: [{
      name: 'Jim',
      children: [{
        name: 'Joe',
        children: [{
          name: 'Lee',
          children: []
        }]
      }]
    },
    {
      name: 'Zoe',
      children: [{
          name: 'Kyle',
          children: [{
            name: 'Tony',
            children: []
          }]
        },
        {
          name: 'Sophia',
          children: [{
            name: 'Thor',
            children: []
          }]
        }
      ]
    }
  ]
}

let res = printChildrenRecursive(tree)
console.log(res);

The console.log outputs

Jim
Joe
Zoe
Kyle
Sophia

But the hasChildren.push only outputs

(2) ["Jim", "Zoe"]

Is printChildrenRecursive is a strange name for a function that should return an array of parents. — Sylwester
– Sylwester, Commented Sep 26, 2020 at 10:56
I know, I was just following a tutorial about printing children but forgot about it as I tried to tinker with the code. — rendell
– rendell, Commented Sep 26, 2020 at 13:58

trincot · Accepted Answer · 2021-12-20 11:57:02Z

3

There are two places where you do not deal well with the array that should be returned:

In the base case, don't just return, but do return []
In the recursive case, don't ignore the value that is returned from the recursive call, but append it to your current array.

Here is the correction:

function printChildrenRecursive(t) {
  let hasChildren = [];
  if (t.children.length === 0) {
    return []; // always return an array!
  }
  t.children.forEach(child => {
    if (child.children.length > 0) {
      console.log(child.name);
      hasChildren.push(child.name);
    }
    // add the returned array: 
    hasChildren.push(...printChildrenRecursive(child));
  })
  return hasChildren;
}

const tree = {name: 'John',children: [{name: 'Jim',children: [{name: 'Joe',children: [{name: 'Lee',children: []}]}]},{name: 'Zoe',children: [{name: 'Kyle',children: [{name: 'Tony',children: []}]},{name: 'Sophia',children: [{name: 'Thor',children: []}]}]}]};

let result = printChildrenRecursive(tree);
console.log(result);

Alternative solution

The algorithm does not return the root node, as it focuses on children -- possibly this is intended.

Also the order of output is a mix of breadth-first and depth-first. The more common order for recursion would be a depth-first order -- like preorder.

And why not use a generator.

Here is an implementation of that:

function *dfs(node) {
    // If you want to include leaves, remove the condition:
    if (node.children.length) yield node.name; 
    for (let child of node.children) yield *dfs(child);
}

const tree = {name: 'John',children: [{name: 'Jim',children: [{name: 'Joe',children: [{name: 'Lee',children: []}]}]},{name: 'Zoe',children: [{name: 'Kyle',children: [{name: 'Tony',children: []}]},{name: 'Sophia',children: [{name: 'Thor',children: []}]}]}]};

let result = Array.from(dfs(tree));
console.log(result);

edited Dec 20, 2021 at 11:57

answered Sep 26, 2020 at 10:25

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sergey Lukin Over a year ago

What about John? It should be added too, no?

trincot Over a year ago

@Sergey, apparently it was not the intention of the Asker to get the root. Their function name hints to this.

Scott Sauyet · Accepted Answer · 2020-09-26 17:37:51Z

Trincot already showed what was wrong with your implementation.

I would like to note that this can be written more simply. Here's a simple recursive function to collect the names of all the parent nodes:

const parents = ({name, children}) => 
  children .length > 0
    ? [name, ... children .flatMap (parents)]
    : []


const tree = {name: 'John', children: [{name: 'Jim', children: [{name: 'Joe', children: [{name: 'Lee', children: []}]}]}, {name: 'Zoe', children: [{name: 'Kyle', children: [{name: 'Tony', children: []}]}, {name: 'Sophia', children: [{name: 'Thor', children: []}]}]}]}

console .log (parents (tree))

If it's possible that some nodes will not have the children property, it's only slightly more complex:

const parents = ({name, children}) => 
  (children || []) .length > 0
    ? [name, ... children .flatMap (parents)]
    : []

If your requirement is to print them, then you can call this and print the results. I would suggest that you make it a habit to separate I/O from the core of your logic.

Collectives™ on Stack Overflow

Trying to extract items from a nested javascript object tree using recursion

2 Answers 2

Alternative solution

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Alternative solution

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related