Home > Back-end >  Recursively get segment of tree according to id
Recursively get segment of tree according to id

Time:10-16

I'm trying to get a tree segment based on an id. The id may be at the root, or anywhere in the children. My goal is to get that entire family tree line, and not other non-related data.

I have the entire data tree, and an id.

The idea is to do this recursively, since the number of children is unknown.

import "./styles.css";

export default function App() {
  const folderTree = [
    {
      id: "1-1",
      children: [
        {
          id: "1-2",
          parentId: "1-1",
          children: []
        }
      ]
    },
    {
      id: "2-1",
      children: [
        {
          id: "2-2",
          parentId: "2-1",
          children: [
            {
              id: "2-4",
              parentId: "2-2",
              children: []
            }
          ]
        },
        {
          id: "2-3",
          parentId: "2-1",
          children: []
        }
      ]
    }
  ];

  const getRelatedTreeFolders = (folders, selectedFolderId) => {
    //** goes top to bottom

    const recursiveChildCheck = (folder, id) => {
      // THIS trial failed
      // let foundNested = false;
      // if (folder.id === id) {
      //   return true;
      // }
      // function recurse(folder) {
      //   if (!folder.hasOwnProperty("children") || folder.children.length === 0)
      //     return;
      //   for (var i = 0; i < folder.children.length; i  ) {
      //     if (folder.children[i].id === id) {
      //       foundNested = true;
      //       break;
      //     } else {
      //       if (folder.children[i].children.length > 0) {
      //         recurse(folder.children[i].children);
      //         if (foundNested) {
      //           break;
      //         }
      //       }
      //     }
      //   }
      // }
      // recurse(folder);
      // return foundNested;

      const aChildHasIt =
        folder.children.length > 0 && folder.children.some((f) => f.id === id);
      if (aChildHasIt) return true;

      let nestedChildHasIt = false;
      /** The problem seems to be here */
      folder.children.forEach((childFolder) => {
        // Is using a forEach loop the correct way?
        // ideally it seems there is a simple way to do a recursive .some on the dhildren...
        childFolder.children.length>0 && recursiveChildCheck(childFolder, id)
      });
      if (nestedChildHasIt) return true;
      folder.children && folder.children.forEach(recursiveChildCheck);
    };

    const treeSegment = folders.reduce((result = [], folder) => {
      if (
        folder.id === selectedFolderId ||
        recursiveChildCheck(folder, selectedFolderId)
      ) {
        result.push(folder);
      }

      return result;
    }, []);

    return treeSegment;
  };

  const selectedFolderId = "2-1";
  const selectedFolderId1 = "2-2";
  const selectedFolderId2 = "2-4";
  const selectedFolderId3 = "2-3";
  const selectedFolderId4 = "3-1";
  const selectedFolderId5 = "1-1";
  const selectedFolderId6 = "1-2";

  console.log("parent");
  console.log(getRelatedTreeFolders(folderTree, selectedFolderId));
  console.log("child");
  console.log(getRelatedTreeFolders(folderTree, selectedFolderId1));
  console.log("grandchild"); // this fails
  console.log(getRelatedTreeFolders(folderTree, selectedFolderId2));
  console.log("sibling");
  console.log(getRelatedTreeFolders(folderTree, selectedFolderId3));
  console.log("not found");
  console.log(getRelatedTreeFolders(folderTree, selectedFolderId4));
  console.log("other parent");
  console.log(getRelatedTreeFolders(folderTree, selectedFolderId5));
  console.log("other child");
  console.log(getRelatedTreeFolders(folderTree, selectedFolderId6));

  return (
    <div className="App">
      <h1>Hello CodeSandbox</h1>
      {/* <h2>{JSON.stringify(result)}</h2> */}
    </div>
  );
}
<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

CodePudding user response:

Some issues:

  • recursiveChildCheck is supposed to return a boolean, but in some cases nothing (undefined) is returned, because a return statement is missing in the following expression:

    folder.children && folder.children.forEach(recursiveChildCheck);
    
  • Moreover, in the expression above, the second operand of the && operator will never be evaluated, because folder.children is an array, and arrays are always truthy, even empty arrays. To give the second operand a chance, the first operand should be folder.children.length > 0

  • But even with that correction, the second operand will always evaluate to undefined, as that is what .forEach returns by design. You should have a method call there that returns a boolean, like some.

  • nestedChildHasIt never gets any other value after its initialisation, and so the following return true will never happen:

    if (nestedChildHasIt) return true;
    

    You may have intended to set nestedChildHasIt to true in the preceding forEach loop, but it seems like you have an alternative way here to do the same as the other forEach loop you had at the end.

I think the issue you have been struggling with is that you need to both check a boolean condition (does the subtree have the id?) and you need to filter the children to the child for which this is true, creating a new node which has this unique child.

Corrected code:

function getForestSegment(nodes, id) {
    function recur(nodes) {
        for (const node of nodes) {
            if (node.id === id) return [node];
            const children = recur(node.children);
            if (children.length) return [{ ...node, children}];
        }
        return [];
    }
    return recur(nodes);
}

// Example from question:
const forest = [{id: "1-1",children: [{id: "1-2",parentId: "1-1",children: []}]},{id: "2-1",children: [{id: "2-2",parentId: "2-1",children: [{id: "2-4",parentId: "2-2",children: []}]},{id: "2-3",parentId: "2-1",children: []}]}];

for (const id of ["2-1", "2-2", "2-4", "2-3", "3-1", "1-1", "1-2"]) {
    console.log(id);
    console.log(getForestSegment(forest, id));
}
<iframe name="sif2" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

  • Related