How do I recursively use Array.prototype.find() while returning a single object?

I know this is an old question, but as another answer recently revived it, I'll another version into the mix.

I would separate out the tree traversal and testing from the actual predicate that we want to test with. I believe that this makes for much cleaner code.

A reduce-based solution could look like this:

const nestedFind = (pred) => (xs) =>
  xs .reduce (
    (res, x) => res ? res : pred(x) ? x : nestedFind (pred) (x.children || []), 
    undefined
  )
 
const findById = (testId) => 
  nestedFind (({id}) => id == testId)


const data = [{id: 1}, {id: 2}, {id: 3}, {id: 4, children: [{id: 6}, {id: 7, children: [{id: 8}, {id: 9}]}]}, {id: 5}]

console .log (findById (8) (data))
console .log (findById (4) (data))
console .log (findById (42) (data))
.as-console-wrapper {min-height: 100% !important; top: 0}

There are ways we could replace that reduce with an iteration on our main list. Something like this would do the same:

const nestedFind = (pred) => ([x = undefined, ...xs]) =>
  x == undefined
    ? undefined
  : pred (x)
    ? x
  : nestedFind (pred) (x.children || []) || nestedFind (pred) (xs)

And we could make that tail-recursive without much effort.

While we could fold the two functions into one in either of these, and achieve shorter code, I think the flexibility offered by nestedFind will make other similar problems easier. However, if you're interested, the first one might look like this:

const findById = (id) => (xs) =>
  xs .reduce (
    (res, x) => res ? res : x.id === id ? x : findById (id) (x.children || []), 
    undefined
  )

I would just use a regular loop and recursive style search:

function findById(data, id) {
    for(var i = 0; i < data.length; i++) {
        if (data[i].id === id) {
            return data[i];
        } else if (data[i].children && data[i].children.length && typeof data[i].children === "object") {
            findById(data[i].children, id);
        }
    }
}

//findById(data, 4) => Object {id: 4, children: Array[2]}
//findById(data, 8) => Object {id: 8}

The problem what you have, is the bubbling of the find. If the id is found inside the nested structure, the callback tries to returns the element, which is interpreted as true, the value for the find.

The find method executes the callback function once for each element present in the array until it finds one where callback returns a true value. [MDN]

Instead of find, I would suggest to use a recursive style for the search with a short circuit if found.

var data = [{ id: 1 }, { id: 2 }, { id: 3 }, { id: 4, children: [{ id: 6 }, { id: 7, children: [{ id: 8 }, { id: 9 }] }] }, { id: 5 }];

function findById(data, id) {
    function iter(a) {
        if (a.id === id) {
            result = a;
            return true;
        }
        return Array.isArray(a.children) && a.children.some(iter);
    }

    var result;
    data.some(iter);
    return result
}

console.log(findById(data, 8));

Let's consider the implementation based on recursive calls:

function findById(tree, nodeId) {
  for (let node of tree) {
    if (node.id === nodeId) return node

    if (node.children) {
      let desiredNode = findById(node.children, nodeId)
      if (desiredNode) return desiredNode
    }
  }
  return false
}

Usage

var data = [
  { id: 1 }, { id: 2 }, { id: 3 },
  { id: 4, children: [
      { id: 6 },
      { id: 7,
        children: [
          { id: 8 }, 
          { id: 9 }
        ]}]},
  { id: 5 }
]

findById(data,  7 ) // {id: 7, children: [{id: 8}, {id: 9}]}
findById(data,  5 ) // {id: 5}
findById(data,  9 ) // {id: 9}
findById(data,  11) // false

To simplify the picture 🐒, imagine that:

  • you are the monkey sitting on the top of a palm tree 🌴;
  • and searching for a ripe banana, going down the tree
  • you are in the end and searches aren't satisfied you;
  • come back to the top of the tree and start again from the next branch;
  • if you tried all bananas on the tree and no one is satisfied you, you just assert that ripe bananas don't grow on this this palm;
  • but if the banana was found you come back to the top and get pleasure of eating it.

Now let's try apply it to our recursive algorithm 🍌:

  1. Start iteration from the top nodes (from the top of the tree);
  2. Return the node if it was found in the iteration (if a banana is ripe);
  3. Go deep until item is found or there will be nothing to deep. Hold the result of searches to the variable (hold the result of searches whether it is banana or just nothing and come back to the top);
  4. Return the searches result variable if it contains the desired node (eat the banana if it is your find, otherwise just remember not to come back down by this branch);
  5. Keep iteration if node wasn't found (if banana wasn't found keep testing other branches);
  6. Return false if after all iterations the desired node wasn't found (assert that ripe bananas doesn't grow on this tree).

Keep learning recursion it seems not easy at the first time 😟 but this technique allows you to solve daily issues in elegant way 😍.

Tags:

Javascript

Recursion

Recent Posts