Javascript Recursion: remove level with only one child

Question

Given the following data structure:

[  
  {  
     "name":"root",
     "children":[  
        {  
           "name":"de",
           "children":[  
              {  
                 "name":"de",
                 "children":[
                    {  
                       "name":"project-1",
                       "children":[  
                       ]
                    },
                    {  
                       "name":"project-2",
                       "children":[  
                       ]
                    }
                 ]
              }
           ]
        }
     ]
  }
]

Expected:

[
  {
     "name":"project-1",
     "children":[
     ]
  },
  {
     "name":"project-2",
     "children":[
     ]
  }
]

I want to remove a level if there is only one child. In this example I want to have a new array that only contains the children of the "root" level without root itself.

I would do that with reduce but still cant wrap my head around reduce in combination with recursion. Any ideas?

sorry, but could you please provide an example of the resultant array you wish to have? thank you! — TheRealOrange, Mar 13 '19 at 10:27
Please, provide the expected array. the code you wrote and current result. — Andam, Mar 13 '19 at 10:29

Doğancan Arabacı · Accepted Answer · 2019-03-13T14:04:55.490

0

You can simply use map and flatten arrays afterwards.
.map(o => o.children).flat()

EDIT: updated answer after figuring out the real question
Still you can use map and flatten logic but in a recursive manner.

function removeSingleChildElms (o) {
  if (!o.children) return

  if (o.children.length === 1) {
      return o.children.map(removeSingleChildElms).flat()
  } else {
    return o.children
  }
}

EDIT2: Some explanation: The problem is transforming array of object(s) into array of different objects. I don't choose reduce, because the problem doesn't care about relationship/logic among sibling elements. It's just about transforming, hence map will just work good enough.

The problem asks to 'skip' objects with 1 child. This is recurring part, meaning: If you see an object satisfying this condition you go deeper for mapping. In any other valid condition, children stay same (else case)

edited Mar 13 '19 at 14:04

answered Mar 13 '19 at 10:42

Doğancan Arabacı

3,934
2
17
25

This doesn't account for data which has children of children – jro Mar 13 '19 at 10:45
He says ''I want to have a new array that only contains the children of the "root" level without root itself.''. This is removing the root level. In input and output the parts 'and so an' remains same – Doğancan Arabacı Mar 13 '19 at 10:48
Well that's just the sample. An algorithm should work for all input. And so on indicates that there are further layers where this algorithm should be applied. OP also states that he wants to use array.reduce and recursion, indicating that he wants to process all layers – jro Mar 13 '19 at 10:52
updaed my answer – Doğancan Arabacı Mar 13 '19 at 13:48

score 0 · Answer 2 · answered Mar 13 '19 at 14:37

Tree transformation can be made easy by breaking the task down into two parts:

a function for transforming a single node
a function for transforming an array of nodes

To transform a single node, we write transform1

if there are no children, we have found a leaf node, return the singleton node
if there is just one child, drop the node and return the transformation of its only child
otherwise, the node has multiple children, call our second function transformAll

const transform1 = ({ children = [], ...node }) =>
  children.length === 0         // leaf
    ? [ node ]
: children.length === 1         // singleton
    ? transform1 (...children)
: transformAll (children)       // default

To transform an array of nodes, we write transformAll -

const transformAll = (arr = []) =>
  arr .flatMap (transform1)

As you can see, transformAll calls transform1, which also calls transformAll. This technique is called mutual recursion and it's a great way to process recursive data structures like the one proposed in your question.

To ensure our function works properly, I've modified the tree to contain more data scenarios. Note, our program works for any nodes with a children property. All other properties are displayed in the result -

const data =
  [ { name: "a"
    , children:
        [ { name: "a.a"
          , children: 
              [ { name: "a.a.a"
                , children: []
                }
              , { name: "a.a.b"
                , foo: 123
                , children: []
                }
              ]
          }
        ]
    }
  , { name: "b"
    , children:
        [ { name: "b.a"
          , children: 
              [ { name: "b.a.a"
                , children: []
                }
              , { name: "b.a.b"
                , children: []
                }
              ]
          }
        , { name: "b.b"
          , children: []
          }
        ]
    }
  , { name: "c"
    , children: []
    }
  ]

We can run transformAll on your data to transform all of the nodes -

transformAll (data)
// [ { name: 'a.a.a' }
// , { name: 'a.a.b', foo: 123 }
// , { name: 'b.a.a' }
// , { name: 'b.a.b' }
// , { name: 'b.b' }
// , { name: 'c' }
// ]

Or to transform a single node, we call transform1 -

transform1 (data[0])
// [ { name: 'a.a.a' }
// , { name: 'a.a.b', foo: 123 }
// ]

transform1 (data[2])
// [ { name: 'c' } ]

Expand the snippet below to verify the results in your own browser -

const data =
  [ { name: "a"
    , children:
        [ { name: "a.a"
          , children: 
              [ { name: "a.a.a"
                , children: []
                }
              , { name: "a.a.b"
                , foo: 123
                , children: []
                }
              ]
          }
        ]
    }
  , { name: "b"
    , children:
        [ { name: "b.a"
          , children: 
              [ { name: "b.a.a"
                , children: []
                }
              , { name: "b.a.b"
                , children: []
                }
              ]
          }
        , { name: "b.b"
          , children: []
          }
        ]
    }
  , { name: "c"
    , children: []
    }
  ]

const transform1 = ({ children = [], ...node }) =>
  children.length === 0         // leaf
    ? [ node ]
: children.length === 1         // singleton
    ? transform1 (...children)
: transformAll (children)       // default

const transformAll = (arr = []) =>
  arr .flatMap (transform1)

console .log (transformAll (data))

// [ { name: 'a.a.a' }
// , { name: 'a.a.b', foo: 123 }
// , { name: 'b.a.a' }
// , { name: 'b.a.b' }
// , { name: 'b.b' }
// , { name: 'c' }
// ]

Javascript Recursion: remove level with only one child

2 Answers2

Linked