I want to get all parent nodes along with its child, using a child id for a given data in javascript

Question

Here is my sample object, suppose If I give the child id "services/bsf/diamSetting" it should return a string like so "nf-bsf -> bsfConfig -> services/bsf/diamSetting"

let arr = [{
  "attr": {
    "id": "nf-bsf",
    "name": "BSF",
    "sequence": 1
  },
  "children": [{
    "attr": {
      "id": "bsfGeneralConfig",
      "name": "General Configurations",
      "sequence": 10
    },
    "children": [{
      "attr": {
        "id": "services/bsf/bsfGlobalCfg",
        "name": "General Settings",
        "topic": "bsf.global.cfg",
        "sequence": 10
      }
    }, {
      "attr": {
        "id": "configurations/bsf/sbiErrorCodes",
        "name": "SBI Error Codes",
        "topic": "bsf.sbi.errorcodes",
        "sequence": 20
      }
    }]
  }, {
    "attr": {
      "id": "services/bsf/conLoggingLevel",
      "name": "Logging Level",
      "topic": "consistent.logging.cfg.topics",
      "sequence": 20
    }
  }, {
    "attr": {
      "id": "bsfServices",
      "name": "Service Configurations",
      "sequence": 30
    },
    "children": [{
      "attr": {
        "id": "services/bsf/managementService",
        "name": "Management Service",
        "topic": "bsf.managementservice",
        "sequence": 10
      }
    }]
  }, {
    "attr": {
      "id": "bsfConfig",
      "name": "Diameter Configurations",
      "sequence": 40
    },
    "children": [{
      "attr": {
        "id": "services/bsf/diamSetting",
        "name": "Settings",
        "topic": "common.diamsetting",
        "sequence": 10
      }
    }, {
      "attr": {
        "id": "configurations/bsf/diamPeerNode",
        "name": "Peer Nodes",
        "topic": "common.public.diampeernode",
        "sequence": 20
      }
    }, {
      "attr": {
        "id": "services/bsf/diamRoutingTable",
        "name": "Routing Table",
        "topic": "common.public.diamroutingtable",
        "sequence": 30
      }
    }, {
      "attr": {
        "id": "configurations/bsf/diamLoadShedding",
        "name": "Load Shedding Profiles",
        "topic": "common.public.diamloadshedding",
        "sequence": 40
      }
    }, {
      "attr": {
        "id": "configurations/bsf/diamMessagePriority",
        "name": "Message Priority Profiles",
        "topic": "common.public.diammessagepriority",
        "sequence": 50
      }
    }]
  }, {
    "attr": {
      "id": "bsf-sessionViewer",
      "name": "Session Viewer",
      "sequence": 50
    }
  }, {
    "attr": {
      "id": "administration",
      "name": "Administration",
      "sequence": 60
    },
    "children": [{
      "attr": {
        "id": "bsfBulkExportImport",
        "name": "Export & Import",
        "sequence": 10
      }
    }]
  }]
}];

I have tried the following to traverse, i either get undefined or some wrong path. i don't even get child node with this, and this will be traversed in a reverse order.

var parent = [];
const findParent = (arr, id) => {
        for (let i=0; i<arr.length; i++) {
          if(arr[i].attr.id == id) {
            return parent;
          } else if (arr[i].children && arr[i].children.length) {
            parent.push(arr[i].attr.id);
            findParent(arr[i].children, id)
          }
        }
      };
let x = findParent(arr, "services/bsf/diamSetting");
console.log(x)

ggorlen · Answer 1 · 2021-08-21T22:40:44.013

Your parent array breaks function encapsulation, creating multiple issues:

It's never popped when a path turns out to be an incorrect one, leading to extra data. This array keeps track of all visited nodes rather than the specific path to the target node.
The function isn't idempotent; after multiple calls, parent may have stale information from a previous traversal.
If this global data name changes, the function breaks. Functions should be able to withstand refactors outside of their scope.

Here's an approach that addresses these problems. I'm using a closure to keep the result array scoped locally to its function, pop to undo every push that didn't wind up leading to the target, and some to bail out from the search and start unwinding the call stack as soon as the target is found.

const tree = [ { "attr": { "id": "nf-bsf", "name": "BSF", "sequence": 1 }, "children": [ { "attr": { "id": "bsfGeneralConfig", "name": "General Configurations", "sequence": 10 }, "children": [ { "attr": { "id": "services/bsf/bsfGlobalCfg", "name": "General Settings", "topic" : "bsf.global.cfg", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/sbiErrorCodes", "name": "SBI Error Codes", "topic" : "bsf.sbi.errorcodes", "sequence": 20 } } ] }, { "attr": { "id": "services/bsf/conLoggingLevel", "name": "Logging Level", "topic": "consistent.logging.cfg.topics", "sequence": 20 } }, { "attr": { "id": "bsfServices", "name": "Service Configurations", "sequence": 30 }, "children": [ { "attr": { "id": "services/bsf/managementService", "name": "Management Service", "topic": "bsf.managementservice", "sequence": 10 } } ] }, { "attr": { "id": "bsfConfig", "name": "Diameter Configurations", "sequence": 40 }, "children": [ { "attr": { "id": "services/bsf/diamSetting", "name": "Settings", "topic": "common.diamsetting", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/diamPeerNode", "name": "Peer Nodes", "topic": "common.public.diampeernode", "sequence": 20 } }, { "attr": { "id": "services/bsf/diamRoutingTable", "name": "Routing Table", "topic": "common.public.diamroutingtable", "sequence": 30 } }, { "attr": { "id": "configurations/bsf/diamLoadShedding", "name": "Load Shedding Profiles", "topic": "common.public.diamloadshedding", "sequence": 40 } }, { "attr": { "id": "configurations/bsf/diamMessagePriority", "name": "Message Priority Profiles", "topic": "common.public.diammessagepriority", "sequence": 50 } } ] }, { "attr": { "id": "bsf-sessionViewer", "name": "Session Viewer", "sequence": 50 } }, { "attr": { "id": "administration", "name": "Administration", "sequence": 60 }, "children": [ { "attr": { "id": "bsfBulkExportImport", "name": "Export & Import", "sequence": 10 } } ] } ] } ];
 
const findPath = (children, targetId) => {
  const path = [];
  (function search(children) {
    return children?.some(child => {
      path.push(child.attr.id);
      
      if (child.attr.id === targetId || search(child.children)) {
        return true;
      }
      
      path.pop();
    });
  })(children);
  return path;
};

const path = findPath(tree, "services/bsf/diamSetting");
console.log(path.join(" -> "));

score 1 · Accepted Answer · answered Aug 21 '21 at 22:07

Using a parent variable outside of the function will break the recursion because each level of recursion shares a common varaible, meaning result of one recursion may overwrite the previous result of another recursion.

You should instead make the parent variable something private to the findParent function itself so that each recursion will create its own array and modify/returns it.

Here's a revised code that make use of a third argument hierarchy that functions the same as your parent, but private to each function call (closure):

const arr = [ { "attr": { "id": "nf-bsf", "name": "BSF", "sequence": 1 }, "children": [ { "attr": { "id": "bsfGeneralConfig", "name": "General Configurations", "sequence": 10 }, "children": [ { "attr": { "id": "services/bsf/bsfGlobalCfg", "name": "General Settings", "topic" : "bsf.global.cfg", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/sbiErrorCodes", "name": "SBI Error Codes", "topic" : "bsf.sbi.errorcodes", "sequence": 20 } } ] }, { "attr": { "id": "services/bsf/conLoggingLevel", "name": "Logging Level", "topic": "consistent.logging.cfg.topics", "sequence": 20 } }, { "attr": { "id": "bsfServices", "name": "Service Configurations", "sequence": 30 }, "children": [ { "attr": { "id": "services/bsf/managementService", "name": "Management Service", "topic": "bsf.managementservice", "sequence": 10 } } ] }, { "attr": { "id": "bsfConfig", "name": "Diameter Configurations", "sequence": 40 }, "children": [ { "attr": { "id": "services/bsf/diamSetting", "name": "Settings", "topic": "common.diamsetting", "sequence": 10 } }, { "attr": { "id": "configurations/bsf/diamPeerNode", "name": "Peer Nodes", "topic": "common.public.diampeernode", "sequence": 20 } }, { "attr": { "id": "services/bsf/diamRoutingTable", "name": "Routing Table", "topic": "common.public.diamroutingtable", "sequence": 30 } }, { "attr": { "id": "configurations/bsf/diamLoadShedding", "name": "Load Shedding Profiles", "topic": "common.public.diamloadshedding", "sequence": 40 } }, { "attr": { "id": "configurations/bsf/diamMessagePriority", "name": "Message Priority Profiles", "topic": "common.public.diammessagepriority", "sequence": 50 } } ] }, { "attr": { "id": "bsf-sessionViewer", "name": "Session Viewer", "sequence": 50 } }, { "attr": { "id": "administration", "name": "Administration", "sequence": 60 }, "children": [ { "attr": { "id": "bsfBulkExportImport", "name": "Export & Import", "sequence": 10 } } ] } ] } ];

const findParent = (
  arr,
  id,
  hierarchy = []  // Use an array here to store parents instead of using an external variable.
) => {
  for (let i = 0; i < arr.length; i++){
    // If id is found, push it to the result array, stop the loop, then return the result.
    if (arr[i].attr.id === id){
      hierarchy.push(arr[i].attr.id);
      return hierarchy;
    }
    
    // If id is not found, proceed to its children
    if (arr[i].children && arr[i].children.length){
      const childResult = findParent(
        arr[i].children,
        id,
        [...hierarchy, arr[i].attr.id]  // Pass the found parents so far to its child recursion.
      );
      
      // Only stop the loop and return the result if id is found in child.
      if (childResult){
        return childResult;
      }
    }
    
    // Proceed to the next loop if id is not found in current item AND its offspring children.
  }

  // Return null if id is not found in this branch.
  return null;
};

let x = findParent(arr, "services/bsf/diamSetting");

console.log(x && x.join(' -> '));

I want to get all parent nodes along with its child, using a child id for a given data in javascript

2 Answers2