Question 173868 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Recursively update parent child info based on key passed

I have an array of object that look this,

const data = [
  {
    key: "id1",
    name: "Category 1",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id2",
        name: "Applications",
        curr: 20,
        total: 30,
        nodes: [
          {
            key: "id3",
            name: "Gaming",
            curr: 5,
            total: 10,
            nodes: []
          },
          {
            key: "id4",
            name: "Operating System",
            curr: 15,
            total: 20,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id5",
    name: "Category 2",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id6",
        name: "Sub Category",
        curr: 12,
        total: 48,
        nodes: [
          {
            key: "id7",
            name: "Inside Sub",
            curr: 12,
            total: 48,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id8",
    name: "Last One",
    curr: 0,
    total: 0,
    nodes: []
  }
];

key property at each level is unique across the entire tree. When I pass in key and this array to a functon, it should increment the curr value at the matching key level and this increment should go all the way upto level 1. Note that level 0 items should not be updated. So basically when I pass incrementRecursively(data, "id4"), the output should look like,

const output = [
  {
    key: "id1",
    name: "Category 1",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id2",
        name: "Applications",
        curr: 21,
        total: 30,
        nodes: [
          {
            key: "id3",
            name: "Gaming",
            curr: 5,
            total: 10,
            nodes: []
          },
          {
            key: "id4",
            name: "Operating System",
            curr: 16,
            total: 20,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id5",
    name: "Category 2",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id6",
        name: "Sub Category",
        curr: 12,
        total: 48,
        nodes: [
          {
            key: "id7",
            name: "Inside Sub",
            curr: 12,
            total: 48,
            nodes: []
          }
        ]
      }
    ]
  },
  {
    key: "id8",
    name: "Last One",
    curr: 0,
    total: 0,
    nodes: []
  }
];

The code that I tried,

const incrementRecursively = (nodes, key) => {
  const increment = (nodes, key) => {
    nodes.forEach((node) => {
      if (node.key === key) {
        node.curr++;
      }
      if (node.nodes.length) {
        increment(node, key);
      }
    });
  };
  increment(nodes, key);
  return nodes;
};

Can someone help how to update the parent and not increment roots value?

Tags:

3

Answers


  1. 0

    Something like this should work:

    function inc(nodes, key, depth = 0) {
    for (let n of nodes)
        if (n.key === key || inc(n.nodes ?? [], key, depth + 1)) {
            if (depth > 0)
                n.curr++
            return true
        }
}

inc(data, 'id7')

    The idea is to return true if the current node has been directly or indirectly incremented so that the parent can update accordingly.

    Login or Signup to reply.
  2. 0

    You could implement a walker to step through the tree.

    const main = () => {
  incrementRecursively(data, 'id4');
  console.log(data);
};

const incrementRecursively = (nodeList, key) => {
  const childPredicate = (node) => node.key === key;
  walkForest(nodeList, (node, parent, depth) => {
    const isChild = depth > 0; /* or parent != null */
    if (isChild && childMatches(node, childPredicate)) {
      node.curr++;
    }
  });
};

// Post-order
const walkTree = (tree, walker, parent = null, depth = 0) => {
  if (tree.nodes?.length) {
    tree.nodes.forEach(node => walkTree(node, walker, tree, depth + 1));
  }
  walker(tree, parent, depth);
};

const walkForest = (forest, walker) => {
  forest.forEach(tree => walkTree(tree, walker));
};

const childMatches = (node, predicate) =>
  predicate(node) || node.nodes.some(child => childMatches(child, predicate));

const data = [{
    key: "id1",
    name: "Category 1",
    curr: 0,
    total: 0,
    nodes: [{
      key: "id2",
      name: "Applications",
      curr: 20,
      total: 30,
      nodes: [{
        key: "id3",
        name: "Gaming",
        curr: 5,
        total: 10,
        nodes: []
      }, {
        key: "id4",
        name: "Operating System",
        curr: 15,
        total: 20,
        nodes: []
      }]
    }]
  },
  {
    key: "id5",
    name: "Category 2",
    curr: 0,
    total: 0,
    nodes: [{
      key: "id6",
      name: "Sub Category",
      curr: 12,
      total: 48,
      nodes: [{
        key: "id7",
        name: "Inside Sub",
        curr: 12,
        total: 48,
        nodes: []
      }]
    }]
  },
  {
    key: "id8",
    name: "Last One",
    curr: 0,
    total: 0,
    nodes: []
  }
];

main();
    .as-console-wrapper { top: 0; max-height: 100% !important; }
    Login or Signup to reply.
  3. 0

    I think this code will do the job:

    (it’s based on @gog answer and is self-explanatory hopefully)

    function inc(nodes, key, depth = 0) {
  for (let n of nodes) {
    const nodeOwnKeyMatches = n.key === key; 
    const nodeChildsKeyMatches = inc(n.nodes, key, depth + 1);

    if (!nodeOwnKeyMatches && !nodeChildsKeyMatches) continue;

    if (nodeOwnKeyMatches || depth > 0) n.curr++;

    return true;
  }
}

const data = [
  {
    key: "id1",
    name: "Category 1",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id2",
        name: "Applications",
        curr: 20,
        total: 30,
        nodes: [
          {
            key: "id3",
            name: "Gaming",
            curr: 5,
            total: 10,
            nodes: [],
          },
          {
            key: "id4",
            name: "Operating System",
            curr: 15,
            total: 20,
            nodes: [],
          },
        ],
      },
    ],
  },
  {
    key: "id5",
    name: "Category 2",
    curr: 0,
    total: 0,
    nodes: [
      {
        key: "id6",
        name: "Sub Category",
        curr: 12,
        total: 48,
        nodes: [
          {
            key: "id7",
            name: "Inside Sub",
            curr: 12,
            total: 48,
            nodes: [],
          },
        ],
      },
    ],
  },
  {
    key: "id8",
    name: "Last One",
    curr: 0,
    total: 0,
    nodes: [],
  },
];

inc(data, "id4");

console.log(data);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search