CODEWITHSUNDEEP
javascripttreereducetraversal
Mr. Polywhirl
Mr. Polywhirl

Reputation: 48600

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

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.

initial state

Before traversal

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

before traversal

After traversal

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

after traversal

Upvotes: 1

Views: 765

Answers (2)

Scott Sauyet
Scott Sauyet

Reputation: 50787

Another approach which treats your tree as immutable (and built out of plain JS objects, not constructed Nodes) can use a simpler recursion for the core of your buildTree and calculateStatus functions. We could write it like this:

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
)

const buildForest = (items, target) =>
  items .filter (({parentId}) => parentId == target) .map (({id, parentId, data}) => ({
    id, 
    parentId, 
    status: maxStatus (data), 
    children: buildForest (items, id)
  }))

// Assumes there really is a single root.
const buildTree = (items) => 
  ({id: 0, parentId: null, status: UNKNOWN, children: buildForest (items, 0)})

const calculateStatus = (node, children = node .children .map (c => calculateStatus (c))) => ({
  ...node,
  status: maxStatus ([node .status, ...children .map (c => c .status)]),
  children,
})

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)
const newTree = calculateStatus (tree)

// stringify just to avoid SO's /**id:N**/ & /**ref:N**/ notation.  Statuses ARE references
// Note that `tree` was not modified in calling `calculateStatus`
console .log (JSON.stringify(tree, null, 4))
printTree (newTree)
.as-console-wrapper {max-height: 100% !important; top: 0}

buildTree is built atop buildForest which recursively scans the list of elements for the next set of children. Note that this creates plain JS objects, and does not use something like your Node constructor.

calculateStatus builds a new node from a current one by first recurring on any children, extracting their status properties, and then calls maxStatus with them and the current node's status to derive the new status. Then it creates a new node with those properties. Note that other properties of the node than children and status will be shared by reference, if they are reference types. (It doesn't matter with this example as id and parentId are primitives. But it does show that this technique reuses as much as it can.)

Because it's being called with map and we add a default parameter, you cannot replace node .children .map (c => calculateStatus (c)) with node .children .map (calculateStatus), which certainly would feel cleaner. If you don't like that default parameter, we could easily recast this as:

const calculateStatus = (node) => {
  const children = node .children .map (calculateStatus)
  return {
    ...node,
    status: maxStatus ([node .status, ...children .map (c => c .status)]),
    children,
  }
}

I left printNode/printTree alone; they work fine with these plain JS objects.

You may not find this of use if you really prefer to mutate your data, but I find it a cleaner way to work.

Update

It wasn't clear to me what was meant by this comment:

I am going to throw the tree away, so mutating it would not be an issue.

But if it meant that the intermediate tree is of no value whatsoever, and is only there as a step to create the final tree, then we can build that final tree directly, with code something like this:

const buildForest = (items, target) => 
  items .filter (({parentId}) => parentId == target) .map (
    ({id, parentId, data}) => {
      const children = buildForest (items, id)
      const status = maxStatus ([...data, ...children .map (c =>  c .status)])
      return {id, parentId, status, children}
    })

const buildTree = (items) => {
  const children = buildForest (items, 0)
  const status = maxStatus (children .map (c => c .status))
  return {id: 0, parentId: null, status, children}
}

Upvotes: 1

trincot
trincot

Reputation: 350202

There are two issues, both in calculateStatus:

  1. It lacks a return statement, and so the recursive call will always return undefined. It should end with return status;

  2. 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);

Upvotes: 1

Related Questions