CODEWITHSUNDEEP
javascriptrecursiontree
rendell
rendell

Reputation: 937

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

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"]

Upvotes: 1

Views: 507

Answers (2)

trincot
trincot

Reputation: 349956

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

  1. In the base case, don't just return, but do return []

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

Upvotes: 3

Scott Sauyet
Scott Sauyet

Reputation: 50787

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.

Upvotes: 1

Related Questions