Javascript - Update the value of parent all the way till the tree based on key

lrr59
May 23, 2023
188 views
0 votes
2 Answers

I have an array of object that look this,

const data = [
  {
    "key": "group1",
    "name": "groupname1",
    "total": 65,
    "available": 34,
    "children": [
      {
        "key": "cat1",
        "name": "category1",
        "total": 5,
        "available": 2,
        "children": []
      },
      {
        "key": "cat2",
        "name": "category2",
        "total": 60,
        "available": 32,
        "children": [
          {
            "key": "cat3",
            "name": "category3",
            "total": 15,
            "available": 12,
            "children": []
          },
          {
            "key": "cat6",
            "name": "category6",
            "total": 55,
            "available": 20,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "key": "group2",
    "name": "groupname2",
    "total": 75,
    "available": 47,
    "children": [
      {
        "key": "cat4",
        "name": "category4",
        "total": 25,
        "available": 22,
        "children": []
      },
      {
        "key": "cat5",
        "name": "category5",
        "total": 50,
        "available": 25,
        "children": []
      }
    ]
  }
]

key property at each level is unique across the entire tree. When I pass in key as a paremeter and this array to a functon, it should increment the available value at the matching key level and this increment should go all the way upto root.So basically when I pass incrementRecursively(data, "cat3"), the output should look like,

[
  {
    "key": "group1",
    "name": "groupname1",
    "total": 65,
    "available": 35,
    "children": [
      {
        "key": "cat1",
        "name": "category1",
        "total": 5,
        "available": 2,
        "children": []
      },
      {
        "key": "cat2",
        "name": "category2",
        "total": 60,
        "available": 33,
        "children": [
          {
            "key": "cat3",
            "name": "category3",
            "total": 15,
            "available": 13,
            "children": []
          },
          {
            "key": "cat6",
            "name": "category6",
            "total": 55,
            "available": 20,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "key": "group2",
    "name": "groupname2",
    "total": 75,
    "available": 47,
    "children": [
      {
        "key": "cat4",
        "name": "category4",
        "total": 25,
        "available": 22,
        "children": []
      },
      {
        "key": "cat5",
        "name": "category5",
        "total": 50,
        "available": 25,
        "children": []
      }
    ]
  }
]

How can I track the parent and update the increments all the way to the root node? Code I tried that doesnt work

function increment(nodes, key, depth = 0) {
  for (let n of nodes) {
    const nodeOwnKeyMatches = n.key === key;
    const nodeChildsKeyMatches = increment(n.children, key, depth + 1);
    if (!nodeOwnKeyMatches && !nodeChildsKeyMatches) continue;
    if (nodeOwnKeyMatches) n.available++;
  }
}

Answers

This is how I’d do it: For each node, check if there is a key match or if one of its children is a key match (recursively). If so, increment the available property of the node and return true to indicate that a match was found.

const data = [{"key":"group1","name":"groupname1","total":65,"available":34,"children":[{"key":"cat1","name":"category1","total":5,"available":2,"children":[]},{"key":"cat2","name":"category2","total":60,"available":32,"children":[{"key":"cat3","name":"category3","total":15,"available":12,"children":[]},{"key":"cat6","name":"category6","total":55,"available":20,"children":[]}]}]},{"key":"group2","name":"groupname2","total":75,"available":47,"children":[{"key":"cat4","name":"category4","total":25,"available":22,"children":[]},{"key":"cat5","name":"category5","total":50,"available":25,"children":[]}]}]

function increment(node, key) {
  return (node.key===key || node.children.some(c=>increment(c, key))) 
    && (node.available++, true)
}

data.forEach(n=>increment(n, 'cat3'))
console.log(data)

As per the comment below, to prevent top-level nodes being incremented as a result of descendent key matches:

const data = [{"key":"group1","name":"groupname1","total":65,"available":34,"children":[{"key":"cat1","name":"category1","total":5,"available":2,"children":[]},{"key":"cat2","name":"category2","total":60,"available":32,"children":[{"key":"cat3","name":"category3","total":15,"available":12,"children":[]},{"key":"cat6","name":"category6","total":55,"available":20,"children":[]}]}]},{"key":"group2","name":"groupname2","total":75,"available":47,"children":[{"key":"cat4","name":"category4","total":25,"available":22,"children":[]},{"key":"cat5","name":"category5","total":50,"available":25,"children":[]}]}]

function increment(node, key, isTopLevel) {
  return (node.key===key || node.children.some(c=>increment(c, key)))
    && (!isTopLevel && node.available++, true)
}

data.forEach(n=>increment(n, 'cat3', true))
console.log(data)

The result is also possible to achieve with a help of Map and a little addition to the structure of the original tree.

let rootBranch = [
  {
    "key": "group1",
    "name": "groupname1",
    "total": 65,
    "available": 35,
    "children": [
      {
        "key": "cat1",
        "name": "category1",
        "total": 5,
        "available": 2,
        "children": []
      },
      {
        "key": "cat2",
        "name": "category2",
        "total": 60,
        "available": 33,
        "children": [
          {
            "key": "cat3",
            "name": "category3",
            "total": 15,
            "available": 13,
            "children": []
          },
          {
            "key": "cat6",
            "name": "category6",
            "total": 55,
            "available": 20,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "key": "group2",
    "name": "groupname2",
    "total": 75,
    "available": 47,
    "children": [
      {
        "key": "cat4",
        "name": "category4",
        "total": 25,
        "available": 22,
        "children": []
      },
      {
        "key": "cat5",
        "name": "category5",
        "total": 50,
        "available": 25,
        "children": []
      }
    ]
  }
];

function prepareForBubbling (rootBranch) {
    let map = new Map();
    function mapChildren (parent) {
        parent.children.forEach((child) => {
            child.parent = parent;
            map.set(child.key, child);
            mapChildren(child);
        });
    }
    rootBranch.forEach((child) => {
        child.parent = null;
        map.set(child.key, child);
        mapChildren(child);
    });
    return map;
}

function bubbleUp (map, key, callback) {
    let nodesProcessed = 0;
    let node = map.get(key);
    let userValue;
    while (node) {
        userValue = callback(node, userValue);
        nodesProcessed++;
        node = node.parent;
    }
    return nodesProcessed;
}

let nodeMap = prepareForBubbling(rootBranch);

// test only nodes without children to make the result easier to visually check
['cat1', 'cat3', 'cat4', 'cat5', 'cat6']
.forEach((key) => bubbleUp(nodeMap, key, (node) => node.available++));
console.log(rootBranch);

Nesting levels:  0                   0
                     1   1               1   1
                             2   2

Initial values:  35  2   33  13  20  47  22  25
Updated values:  38  3   35  14  21  49  23  26

Please signup or login to give your own answer.

Click here to cancel reply.

Javascript – Update the value of parent all the way till the tree based on key

Answers