find in deep nested array (tree) recursivley

Question

I want to find a value in the following nested array without using loops:

let children = [
  {
    name: 'grand 1',
    children: [
      {
        name: 'parent 1.1',
        children: [
          {
            name: 'child 1.1.1',
            children: [
              // more...
            ]
          },
          // more...
        ],
      },
      // more...
    ],
  },
  // more...
];

This is what I'd do if I was only searching in the horizontal axis:

let childrenHorizontal = [
  { name: 'grand 1' },
  { name: 'grand 2' },
  { name: 'grand 3' },
  // more
];

function findHorizontal(name, childrenHorizontal) {
  let [head, ...tail] = childrenHorizontal;
  if (head.name === name)
    return head;
  else if (tail.length)
    return findHorizontal(name, tail);
}

But how do I search the nested array both horizontally and vertically?

Answer 1

A bit more generically, we can write a deepFind function that takes an arbitrary predicate and returns a function that tests a tree in a depth-first manner until it finds a matching node, returning undefined if no match is found. (This is JS, after all!) Then we can write findByName as a function that that takes a target name and passes to deepFind a function that tests whether a given node's name matches that target. It might look like this:

const deepFind = (pred) => ([head, ...tail]) =>
  head == undefined
    ? undefined 
  : pred (head) 
    ? head 
  : deepFind (pred) (head .children) || deepFind (pred) (tail)

const findByName = (target) => deepFind (({name}) => name == target)

let children = [{name: 'grand 1', children: [{name: 'parent 1.1', children: [{name: 'child 1.1.1', children: []}]}, {name: 'parent 1.2', children: []}]}]


console .log ('parent 1.1:', findByName ("parent 1.1") (children))
console .log ('child 1.1.1:', findByName ("child 1.1.1") (children))
console .log ('parent 1.2:', findByName ("parent 1.2") (children))

.as-console-wrapper {max-height: 100% !important; top: 0}

(Note that I added a parent 1.2 node in the obvious location in the tree to demonstrate searching multiple children of one node.)

This finds the first node in a pre-order traversal of the tree that matches our predicate. We use the short-circuiting feature of JavaScript's || operator to stop as soon as we've found a match.