How does one, within a nested data-structure of parent-objects and child-arrays, find a data-item by a specific (unique) key-value pair?

Question

Given is a data-structure as follows ...

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [{
    name: "file.txt",
    type: "file",
    full: "/home/adityam/Documents/file.txt",
  }, {
    name: "anotherFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder",
    children: [],
  }],
};

... but object properties might change in value and vary by name (key) and count (amount of entries).

What's stable though, is the base data-structure with an object's/item's full property (string value) and the possible presence of a children property (array type, empty of not).

In order to later change a data-item's value one needs to first find/retrieve the former from the nested data-structure by e.g. an item's known full property value.

In case of an item like ...

{
  name: "anotherFolder",
  type: "dir",
  full: "/home/adityam/Documents/anotherFolder",
  children: [],
}

... where one wants to change e.g. children, the item first needs to be found/retrieved via its known full property value of "/home/adityam/Documents/anotherFolder".

How would one achieve such a task?

Answer 1

Searching for the node

Recursion!

You can find a reference for such a tree node with a recursive (search) function:

All recursive algorithms must obey three important laws:

1. A recursive algorithm must call itself, recursively.
2. A recursive algorithm must have a base case.
3. A recursive algorithm must change its state and move toward the base case.

For example findNodeRecursive(name, node):

1. If property full of node equals name, return node. (Base case: Found)
2. If property type of node is not "dir", return null. (Base case: Cannot be inside)
3. For each element childNode of property children of node: (Moving toward some base case)
   1. Let result be the result of the call findNodeRecursive(name, childNode). (Recursive call)
   2. If result is not null, return result. (Base case: Found in children)
4. Return null. (Base case: Not found)

// Implementation of the algorithm above
function findNodeRecursive(fullName, node) {
  if (node.full === fullName) return node;
  if (node.type !== "dir") return null;
  
  for (const childNode of node.children) {
    const result = findNodeRecursive(fullName, childNode);
    if (result !== null) return result;
  }
  
  return null;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [
    {
      name: "file.txt",
      type: "file",
      full: "/home/adityam/Documents/file.txt",
    },
    {
      name: "anotherFolder",
      type: "dir",
      full: "/home/adityam/Documents/anotherFolder",
      children: []
    }
  ]
};

console.log(findNodeRecursive("/home/adityam/Documents/anotherFolder", tree));

Iteratively

There is also an iterative solution, which requires flattening the tree to a flat array, and then search for the node by its name.

Flattening can be done in multiple ways, either recursively again, or iteratively.

function findNodeIterative(name, node) {
  const nodes = [node];
  
  // Iterative flattening
  for (let i = 0; i < nodes.length; ++i) {
    if (nodes[i].children) nodes.push(...nodes[i].children);
  }
  
  return nodes.find(n => n.full === name);
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [
    {
      name: "file.txt",
      type: "file",
      full: "/home/adityam/Documents/file.txt",
    },
    {
      name: "anotherFolder",
      type: "dir",
      full: "/home/adityam/Documents/anotherFolder",
      children: []
    }
  ]
};

console.log(findNodeIterative("/home/adityam/Documents/anotherFolder", tree));

Modifying children

The value of children is an array. If you want to modify this array, you can use one of its mutating methods, for example Array.splice().

// Reference found with some function, for example the above findByName()
const node = {
  name: "anotherFolder",
  type: "dir",
  full: "/home/adityam/Documents/anotherFolder",
  children: []
};

const nodesToAdd = [
  {
    name: "someFile.txt",
    type: "file",
    full: "/home/adityam/Documents/anotherFolder/someFile.txt"
  },
  {
    name: "someFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder/someFolder",
    children: []
  }
];

console.log("Before modifying:\nNode:", node);
node.children.splice(0, 0, ...nodesToAdd);
console.log("After modifying:\nNode:", node);

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

Answer 2

The OP's actual use case seems to be finding an array's data-item within a nested data-structure of unknown depth of the form ...

{
  /* data-item or root-object/node */
  additionalKey: "value-pair(s)",
  children: [{
    /* data-item */
    additionalKey: "value-pair(s)",
    children: [
      /* optional and possibly empty `children` array */
    ],
  }],
}

... in order to later manipulate the returned matching sub-data-structure. The current use case is to find such an item based on any item's unique key-value pair of the full property.

Though this can be done very easily with a recursive approach, the hereby provided generic implementation allows searching by a to be passed configuration which allows custom values for a data-structure's child-array name (here ... { arrKey: 'children' }) and of a props property which either partially or fully covers a to be matched item's properties/entries signature (here, e.g. ... { full: '/home/adityam/Documents/file.txt' } or even { name: 'Documents', type: 'dir' } ).

The find function itself is implemented in a way that it accepts any type as 1st argument and the finder configuration as its 2nd. If the first argument was an array-type then its find method is going to execute the implemented find function self-recursively. For any other object type (except the null value) an if clause iterates over the provided props' entries in order to assure that every of the props' key-value pairs has a matching counterpart in the passed and currently processed type (the function's first passed argument). In case the current sub-data-item's type does not match, another self recursion takes place; this time with a possible present child array which gets accessed via the currently processed type and the configuration's arrKey value.

As soon as a match got found the configuration which is passed with every recursion gets assigned the matching sub-structure's reference as finder.match. The latter also serves as the recursive find function's only return value which also makes sure that an array's find process will exit early.

function recursivelyFindArrayItemByProperties(type, finder) {
  const { arrKey, props } = finder;

  if (Array.isArray(type)) {
    type
      // find will exit early.
      .find(item =>
        !!recursivelyFindArrayItemByProperties(item, finder)
      );
  } else if (type && ('object' === typeof type)) {
    if (
      Object
        .entries(props)
        .every(([key, value]) => type[key] === value)
    ) {
      finder.match = type;
    } else {
      recursivelyFindArrayItemByProperties(type[arrKey], finder);
    }    
  }
  return finder.match;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [{
    name: "file.txt",
    type: "file",
    full: "/home/adityam/Documents/file.txt",
  }, {
    name: "anotherFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder",
    children: [{
      name: "fooBar.txt",
      type: "file",
      full: "/home/adityam/Documents/fooBar.txt",
    }, {
      name: "bazBiz.txt",
      type: "file",
      full: "/home/adityam/Documents/bazBiz.txt",
    }],
  }],
};

console.log(
  'found by ... { full: "/home/adityam/Documents/fooBar.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/fooBar.txt",
    },
  })
);
console.log(
  'found by ... { full: "/home/adityam/Documents/bazBiz.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/bazBiz.txt",
    },
  })
);

console.log(
  '\nfound by ... { full: "/home/adityam/Documents/file.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/file.txt",
    },
  })
);

console.log(
  '\nfound by ... { full: "/home/adityam/Documents/anotherFolder" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/anotherFolder",
    },
  })
);
console.log(
  'found by ... { full: "/home/adityam/Documents" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents",
    },
  })
);

console.log(
  '\nfound by ... { name: "anotherFolder", type: "dir" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      name: "anotherFolder",
      type: "dir",
      // full: "/home/adityam/Documents/anotherFolder",
    },
  })
);
console.log(
  'found by ... { name: "Documents", type: "dir" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      name: "Documents",
      type: "dir",
      // full: "/home/adityam/Documents",
    },
  })
);

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

Knowing all this, one of cause now could refactor the current find implementation which returns a single, namely the very first matching sub-structure's, reference into a match solution which recursively collects any matching sub-structure's reference.

function recursivelyMatchArrayItemsByProperties(type, finder) {
  const { arrKey, props } = finder;

  if (Array.isArray(type)) {
    type
      .filter(item =>
        !!recursivelyMatchArrayItemsByProperties(item, finder)
      );
  } else if (type && ('object' === typeof type)) {
    if (
      Object
        .entries(props)
        .every(([key, value]) => type[key] === value)
    ) {
      (finder.matches ??= []).push(type);
    } else {
      recursivelyMatchArrayItemsByProperties(type[arrKey], finder);
    }    
  }
  return finder.matches;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [{
    name: "file.txt",
    type: "file",
    full: "/home/adityam/Documents/file.txt",
  }, {
    name: "anotherFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder",
    children: [{
      name: "fooBar.txt",
      type: "file",
      full: "/home/adityam/Documents/fooBar.txt",
    }, {
      name: "bazBiz.txt",
      type: "file",
      full: "/home/adityam/Documents/bazBiz.txt",
    }],
  }],
};

console.log(
  'matches by ... { full: "/home/adityam/Documents/fooBar.txt" } ... ',
  recursivelyMatchArrayItemsByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/fooBar.txt",
    },
  })
);
console.log(
  'matches by ... { type: "file" } ... ',
  recursivelyMatchArrayItemsByProperties(tree, {
    arrKey: 'children',
    props: {
      type: "file",
    },
  })
);
console.log(
  'matches by ... { type: "dir" } ... ',
  recursivelyMatchArrayItemsByProperties(tree, {
    arrKey: 'children',
    props: {
      type: "dir",
    },
  })
);

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

Answer 3

As others have already answered, I will post the answer that I wrote earlier, but would usually not post until the OP showed an attempt.

---

I think we're best off breaking apart the tree navigation code from the code that checks if we're at the right node and from the code that modifies a node.

Since I don't know what sort of modification you are interested in performing, I just add a notice property to the object, but you can use any function that returns a new version of the object, whether an altered clone, a reference to a mutated original, or something else entirely. Here's an example:

const modifyNode = (pred, fn) => (node, _, __,
  {children = [], ...rest} = node, 
  kids = children .map (modifyNode (pred, fn))
) => pred (node)
  ? fn (node)
  : {...rest, ...(kids .length ? {children: kids} : {})}

const modifyByPath = (path) => modifyNode (
  (node) => node.full === path, 
  (node) => ({...node, notice: '*** this was modified ***'})
)


var tree = {name: "Documents", type: "dir", full: "/home/adityam/Documents", children: [{name: "file.txt", type: "file", full: "/home/adityam/Documents/file.txt", }, {name: "anotherFolder", type: "dir",full: "/home/adityam/Documents/anotherFolder", children: [/* ... */]}]}

console .log (modifyByPath ('/home/adityam/Documents/anotherFolder') (tree))

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

We have a utility function modifyNode that accepts a predicate function to test whether we've hit the right node and a modification function that takes a node and returns a node, replaced or altered as desired. It returns a function that takes a node recursively configured with children arrays of objects (themselves with the same structure) and returns an altered version of your tree with every matching node replaced with the result of calling your modification function.

Our main function, modifyByPath, accepts a full path name and calls modifyNode with a simple test predicate and a dummy modification function, which returns a function that does our main work. We will call it like modifyByPath (path) (tree).