find in deep nested array (tree) recursivley-CodePudding

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?

CodePudding user response：

Ok I figured it out. The trick is to concatenate the two axes:

function find(name, children) {
  let [head, ...tail] = children;
  if (head.name === name)
    return head;
  return find(name, [...head.children, ...tail]);
}

CodePudding user response：

You need to use recursion :

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

const find = (name, children) => {
  for (const child of children) {
    // if the chidren's name corresopnds to the one provided, return it
    if (child.name === name) return child

    // here is the recursion
    const e = find(name, child.children)

    // if we found it on the child, we return the one found, else we keep going
    if (e) return e
  }

  // if none of the children or grand-children ... found, return null
  return null
}

console.log(find('parent 1.1', data))

CodePudding user response：

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.