recursively find parents in JSON array backward connect by prev value

Issue

[
  {
    "secCode": 2,
    "secName": "GENERAL NURSING CARE SECTION",
    "prevSec": 0,

  },
  {
    "secCode": 1,
    "secName": "CRITICAL CARE NURSING SECTION",
    "prevSec": 0,
    "children": [
      {
        "secCode": 3,
        "secName": "OPERATION THEATRE",
        "prevSec": 1,
        "children": [
          {
            "secCode": 5,
            "secName": "MAIN OPERATION THEATRE",
            "prevSec": 3,
            "estCode": 152,

          },
          {
            "secCode": 6,
            "secName": "DAY CARE DT SERVICE",
            "prevSec": 3,

          }
        ]
      },
      {
        "secCode": 4,
        "secName": "CRITICAL CARE SERVICES",
        "prevSec": 1,
        "children": [
          {
            "secCode": 675,
            "secName": "Test",
            "prevSec": 4,
            "children": [
              {
                "secCode": 676,
                "secName": "Test1",
                "prevSec": 675,

              },
              {
                "secCode": 677,
                "secName": "Test 2",
                "prevSec": 675,

              },
              {
                "secCode": 678,
                "secName": "Test 3",
                "prevSec": 675,

              },
              {
                "secCode": 679,
                "secName": "Test 4",
                "prevSec": 675,

              }
            ]
          },
          {
            "secCode": 7,
            "secName": "ACUTE CARE",
            "prevSec": 4,

          }
        ]
      }
    ]
  }
]

This is the tree json tree structure. Here each node connected to its parent using prevSec value recursively backward.
For secCode 7 its parents tree will be [7, 4, 1] – connected by secCode = prevSec.
For secCode 679 its parents will be [679, 675, 4, 1]
For secCode 2 its parents will be [2]

I had tried this solution which is partial

 getParent(arr, childSecCode) {

        if (childSecCode == 0) {
          return;
        } else {
          let val = arr.find(item => {
           childSecCode === item.secCode;
          });
          if (val) {
            //arr.find(item => childSecCode == item.secCode).showChildren = true;
           /*  if(check ==0)
            arr.find(item => childSecCode == item.secCode).className = "selected"; */
            this.getParent(arr, val.prevSec);
          }
        }
      }

This will not work as find doesn’t check for children.

How can I achieve the desired result.

Solution

If you want to avoid a search through the whole tree whenever you need this, it is better to first preprocess your tree, so that you can find any node (object) directly, in constant time, given its secCode.

You can create a Map for that connection between secCode and node:

// Creates a map which is keyed by secCode, and for a secCode provides 
//   the corresponding node from the tree
function createMap(tree) {
    let map = new Map;
    
    function recur(node) {
        map.set(node.secCode, node);
        if (node.children) node.children.forEach(recur);
    }
    
    tree.forEach(recur);
    return map;
}

// Uses the map to walk up the tree
function getParents(secCode, map) {
    let parents = [];
    while (secCode) {
        parents.push(secCode);
        let node = map.get(secCode);
        secCode = node.prevSec;
    }
    return parents;
}

// The tree from the question:
let tree = [{"secCode": 2,"secName": "GENERAL NURSING CARE SECTION","prevSec": 0,},{"secCode": 1,"secName": "CRITICAL CARE NURSING SECTION","prevSec": 0,"children": [{"secCode": 3,"secName": "OPERATION THEATRE","prevSec": 1,"children": [{"secCode": 5,"secName": "MAIN OPERATION THEATRE","prevSec": 3,"estCode": 152,},{"secCode": 6,"secName": "DAY CARE DT SERVICE","prevSec": 3,}]},{"secCode": 4,"secName": "CRITICAL CARE SERVICES","prevSec": 1,"children": [{"secCode": 675,"secName": "Test","prevSec": 4,"children": [{"secCode": 676,"secName": "Test1","prevSec": 675,},{"secCode": 677,"secName": "Test 2","prevSec": 675,},{"secCode": 678,"secName": "Test 3","prevSec": 675,},{"secCode": 679,"secName": "Test 4","prevSec": 675,}]},{"secCode": 7,"secName": "ACUTE CARE","prevSec": 4,}]}]}];
// Preprocessing
let map = createMap(tree);
// Example calls:
console.log(getParents(7, map));
console.log(getParents(679, map));

Note that the tree in your example does not have 4 as a child of 3 as your examples suggest — 4 is a child of 1.

If you have a class, you can of course create that map in its constructor and assign it to a property:

class Tree {
    constructor(data) {
        this.map = new Map;

        const recur = (node) => {
            this.map.set(node.secCode, node);
            if (node.children) node.children.forEach(recur);
        }

        data.forEach(recur);
    }
    getParents(secCode) {
        let parents = [];
        while (secCode) {
            parents.push(secCode);
            secCode = this.map.get(secCode).prevSec;
        }
        return parents;
    }
}

// The tree from the question:
let data = [{"secCode": 2,"secName": "GENERAL NURSING CARE SECTION","prevSec": 0,},{"secCode": 1,"secName": "CRITICAL CARE NURSING SECTION","prevSec": 0,"children": [{"secCode": 3,"secName": "OPERATION THEATRE","prevSec": 1,"children": [{"secCode": 5,"secName": "MAIN OPERATION THEATRE","prevSec": 3,"estCode": 152,},{"secCode": 6,"secName": "DAY CARE DT SERVICE","prevSec": 3,}]},{"secCode": 4,"secName": "CRITICAL CARE SERVICES","prevSec": 1,"children": [{"secCode": 675,"secName": "Test","prevSec": 4,"children": [{"secCode": 676,"secName": "Test1","prevSec": 675,},{"secCode": 677,"secName": "Test 2","prevSec": 675,},{"secCode": 678,"secName": "Test 3","prevSec": 675,},{"secCode": 679,"secName": "Test 4","prevSec": 675,}]},{"secCode": 7,"secName": "ACUTE CARE","prevSec": 4,}]}]}];
// Preprocessing
let tree = new Tree(data);
// Example calls:
console.log(tree.getParents(7));
console.log(tree.getParents(679));

Answered By – trincot

Answer Checked By – Terry (AngularFixing Volunteer)

Leave a Reply

Your email address will not be published.