Reduce a tree by recursively rolling up the parent's child nodes

July 7, 2022

Attempting to reduce a flat list of items (each with a list of their own statuses) into a tree, where the status of the child node influences the parent.

const Status = {
  UNKNOWN : { name: 'UNKNOWN' , priority: 0 },
  DEBUG   : { name: 'DEBUG'   , priority: 1 },
  INFO    : { name: 'INFO'    , priority: 2 },
  WARNING : { name: 'WARNING' , priority: 3 },
  ERROR   : { name: 'ERROR'   , priority: 4 },
};

const { UNKNOWN, DEBUG, INFO, WARNING, ERROR } = Status;

const maxStatus = (statuses) =>
  statuses.reduce((max, curr) =>
    curr.priority > max.priority
      ? curr
      : max, UNKNOWN);

class Node {
  constructor({ id, parentId, status }) {
    this.id = id;
    this.parentId = parentId;
    this.status = status ?? UNKNOWN;
    this.children = [];
  }
};

const buildTree = (items) => {
  const
    root = new Node({ id: 0, parentId: null }),
    nodeList = { 0 : root };
  items.forEach(({ id, parentId, data }) => {
    if (!nodeList[id]) {
      nodeList[id] = new Node({
        id,
        parentId,
        status: maxStatus(data)
      });
    } else {
      Object.assign(nodeList[id], {
        parentId,
        status: maxStatus(data)
      });
    }
    if (!nodeList[parentId]) {
      nodeList[parentId] = new Node({ id: parentId });
    }
    nodeList[parentId].children.push(nodeList[id]);
  });
  return root;
};

const calculateStatus = (tree) => {
  let status = UNKNOWN;
  if (tree.children.length) {
    tree.children.forEach(child => {
      const localMax = calculateStatus(child);
      status = maxStatus([ status, localMax ]);
    });
    tree.status = status;
  }
}

const printNode = (node, depth) => {
  const indent = '  '.repeat(depth);
  const { id, status: { name } } = node;
  console.log(`${indent}${id} ${name}`);
  node.children.forEach(child =>
    printNode(child, depth + 1));
}

const printTree = (tree) => printNode(tree, 0);

const items = [
  { id:  1, parentId: 0, data: [ ] },
  { id:  2, parentId: 0, data: [ DEBUG, DEBUG ] },
  { id:  3, parentId: 0, data: [ INFO, DEBUG ] },
  { id:  4, parentId: 1, data: [ INFO, DEBUG ] },
  { id:  5, parentId: 1, data: [ DEBUG ] },
  { id:  6, parentId: 1, data: [ WARNING ] },
  { id:  7, parentId: 2, data: [ INFO, DEBUG ] },
  { id:  8, parentId: 7, data: [ DEBUG ] },
  { id:  9, parentId: 8, data: [ ] },
  { id: 10, parentId: 3, data: [ ERROR, ERROR ] },
]; 

const tree = buildTree(items);

printTree(tree);

.as-console-wrapper { top: 0; max-height: 100% !important; }

Expected output

0 ERROR
  1 WARNING
    4 INFO
    5 DEBUG
    6 WARNING
  2 INFO
    7 INFO
      8 DEBUG
        9 UNKNOWN
  3 ERROR
    10 ERROR

Visual flow

Here is a graphical representation of the algorithm:

Initial state

The initial status shows each node as UNKNOWN.

Before traversal

Before the tree is traversed, each node has a pre-calculated status based on its data.

After traversal

While traversing the tree (recursively) in a post-order traversal strategy, each node asks its children what their maximum status is.

>Solution :

There are two issues, both in calculateStatus:

It lacks a return statement, and so the recursive call will always return undefined. It should end with return status;
The initial value of status should not be UNKNOWN. When at a leaf, and tree.children.length is zero, you don’t want to return UNKNOWN, but the actual status property value of the node. So start with let status = tree.status

Corrected:

const calculateStatus = (tree) => {
  let status = tree.status; // <--
  if (tree.children.length) {
    tree.children.forEach(child => {
      const localMax = calculateStatus(child);
      status = maxStatus([ status, localMax ]);
    });
    tree.status = status;
  }
  return status; // <--
}

And of course, you need to call calculateStatus in the main code.

const Status = {
  UNKNOWN : { name: 'UNKNOWN' , priority: 0 },
  DEBUG   : { name: 'DEBUG'   , priority: 1 },
  INFO    : { name: 'INFO'    , priority: 2 },
  WARNING : { name: 'WARNING' , priority: 3 },
  ERROR   : { name: 'ERROR'   , priority: 4 },
};

const { UNKNOWN, DEBUG, INFO, WARNING, ERROR } = Status;

const maxStatus = (statuses) => {
  return statuses.reduce((max, curr) =>
    curr.priority > max.priority
      ? curr
      : max, UNKNOWN);
};
class Node {
  constructor({ id, parentId, status }) {
    this.id = id;
    this.parentId = parentId;
    this.status = status ?? UNKNOWN;
    this.children = [];
  }
};

const buildTree = (items) => {
  const
    root = new Node({ id: 0, parentId: null }),
    nodeList = { 0 : root };
  items.forEach(({ id, parentId, data }) => {
    if (!nodeList[id]) {
      nodeList[id] = new Node({
        id,
        parentId,
        status: maxStatus(data)
      });
    } else {
      Object.assign(nodeList[id], {
        parentId,
        status: maxStatus(data)
      });
    }
    if (!nodeList[parentId]) {
      nodeList[parentId] = new Node({ id: parentId });
    }
    nodeList[parentId].children.push(nodeList[id]);
  });
  return root;
};

const calculateStatus = (tree) => {
  let status = tree.status; // <--
  if (tree.children.length) {
    tree.children.forEach(child => {
      const localMax = calculateStatus(child);
      status = maxStatus([ status, localMax ]);
    });
    tree.status = status;
  }
  return status; // <--
}

const printNode = (node, depth) => {
  const indent = '  '.repeat(depth);
  const { id, status: { name } } = node;
  console.log(`${indent}${id} ${name}`);
  node.children.forEach(child =>
    printNode(child, depth + 1));
}

const printTree = (tree) => printNode(tree, 0);

const items = [
  { id:  1, parentId: 0, data: [ ] },
  { id:  2, parentId: 0, data: [ DEBUG, DEBUG ] },
  { id:  3, parentId: 0, data: [ INFO, DEBUG ] },
  { id:  4, parentId: 1, data: [ INFO, DEBUG ] },
  { id:  5, parentId: 1, data: [ DEBUG ] },
  { id:  6, parentId: 1, data: [ WARNING ] },
  { id:  7, parentId: 2, data: [ INFO, DEBUG ] },
  { id:  8, parentId: 7, data: [ DEBUG ] },
  { id:  9, parentId: 8, data: [ ] },
  { id: 10, parentId: 3, data: [ ERROR, ERROR ] },
]; 

const tree = buildTree(items);
calculateStatus(tree); // <--
printTree(tree);