Friday, August 19, 2022

Recursive Tree Node Processing in Angular

Part 1: Persisting Selected Nodes

If you look for them, you WIll find tree structures all over the place – from nature, to cities and their neighborhoods, to your own family’s genealogy (i.e., your family tree). Unsurprisingly, trees crop up just as often in programmatic data structures; for instance, in the Document Object Model (DOM):

DOM Tree Structure

 

In coding languages such as JavaScript and TypeScript, trees are usually represented using an array of arrays and/or objects whose keys are comprised of other arrays and/or objects.

A common technique employed when working with tree structures is recursion, whereby a function calls itself. While not the only solution, in many cases, it is the simplest approach. Sound complicated? Fear not: recursion is actually relatively easy to get the hang of, once you have worked through it a couple of times.

To that end, in this two-part web development tutorial series, we will be mapping a complex tree to a more simplistic one, and then back again. In this first installment, we will cover the basic structure of the recursive function and then put it to use to persist the array of VehicleNodes that was introduced in the Tracking Selections with Checkboxes in Angular article back in December. In part 2, we will reconstitute the original VehicleNodes tree from the saved selections.

Trees vs. Tree Arrays in Angular

For the purposes of review, here is the VehicleNode interface and tree that we will be working with in this series:

interface VehicleNode {
  name: string;
  id: number | string;
  children?: VehicleNode[];
  selected?: boolean;
  indeterminate?: boolean;
  parent?: VehicleNode;
}

const TREE_DATA: VehicleNode[] = [
  {
    name: 'Infiniti',
    children: [
      {
        name: 'G50',
        children: [
          { name: 'Pure AWD', id: 1 },
          { name: 'Luxe', id: 2 },
        ],
      },
      {
        name: 'QX50',
        children: [
          { name: 'Pure AWD', id: 3 },
          { name: 'Luxe', id: 4 },
        ],
      },
    ],
  },
  {
    name: 'BMW',
    children: [
      {
        name: '2 Series',
        children: [
          { name: 'Coupé', id: 5 },
          { name: 'Gran Coupé', id: 6 },
        ],
      },
      {
        name: '3 Series',
        children: [
          { name: 'Sedan', id: 7 },
          { name: 'PHEV', id: 8 },
        ],
      },
    ],
  },
];

Technically, all trees have a trunk – that is to say, a single root node. In your family tree, that node would be you. In the above structure, that would be each automobile manufacturer, i.e., Infiniti and BMW. Hence, we can think of our data structure as an array of trees, rather than a single tree. This should become fairly obvious if we unpack the array and reconstruct it using the separate tree objects:

const infiniti =  {
  name: 'Infiniti',
  children: [
    {
      name: 'G50',
      children: [
        { name: 'Pure AWD', id: 1 },
        { name: 'Luxe', id: 2 },
      ],
    },
    {
      name: 'QX50',
      children: [
        { name: 'Pure AWD', id: 3 },
        { name: 'Luxe', id: 4 },
      ],
    },
  ],
};
const bmw = {
  name: 'BMW',
  children: [
    {
      name: '2 Series',
      children: [
        { name: 'Coupé', id: 5 },
        { name: 'Gran Coupé', id: 6 },
      ],
    },
    {
      name: '3 Series',
      children: [
        { name: 'Sedan', id: 7 },
        { name: 'PHEV', id: 8 },
      ],
    },
  ],
};
const TREE_DATA: VehicleNode[] = [infiniti, bmw];

It is well worth distinguishing between the two, as their handling differs slightly.

Read: Manipulate DOM Tree Elements without Writing JavaScript

Anatomy of a Recursive Function in Angular

While the exact code of a recursive function will largely depend on what it is designed to do, as well as the exact structure of the tree, we can give a fast and loose approximation of what such a function might look like:

function callRecursively(node: Object) {
  doSomethingWithNode;
  if (node.hasChildren) {
    node.children.forEach(childNode => {
      this. callRecursively(childNode);
    });
  }
}

To apply the callRecursively() function to an array of tree objects, all that is required is to deal with each tree of the array within a loop. Here is an example of pseudo-code that employs forEach():

TREE_DATA.forEach(node => {
  callRecursively(node);
});

Read: Getting Fancy with the JavaScript FOR Loop

Saving Node Selections in Angular

To gain familiarity with the process of developing a recursive function based on the above template, we will refactor the app that we built in the Tracking Selections with Checkboxes in Angular article so that vehicle selections can be persisted to and recalled from a list of links. Here is what the finished app will look like:

Angular Tree Structures

 

In the above image, we can see a list of saved selections at the top of the tree control as well as a button and text input field for saving the current selections. By examining the format of the saved Infiniti Selections, we can glean an understanding of the saved object format:

public savedSelections: SavedSelection[] = [
 {
    name: "Infinity Selections",
    selections: [{
      id: "infiniti",
      children: [
        {
          id: "g50",
          children: [ { id: 2 } ]
        },
        { id: "qx50" }
      ]
    }]
  },
  // ...
}

The object structure closely resembles that of the TREE_DATA, but with a couple of key differences:

  1. The overall structure is based on the SavedSelection interface:
    interface SavedSelection {
      name: string;
      selections: VehicleSelection[];
    }
    
  2. Selections are stored as an array of objects based on the VehicleSelection interface:
    interface VehicleSelection {
      id: number | string;
      children?: VehicleSelection[];
    }
    

    These include an id, which we will use for looking up VehicleNodes in the TREE_DATA.

  3. Only selected nodes are included; all others are ignored so that stored objects do not eat up memory unnecessarily.

There is only one problem with the current approach: the TREE_DATA does not include ids! Let’s remedy that by adding some now:

Dom and Angular Tree Tutorial

 

Sure, we could use the name field for lookups, but experience dictates that it is never wise to use names for lookups as these can change over time and may require translation at some point.

Read: Filter DOM Nodes Using a TreeWalker

The save() Function in Angular

With that done, we are ready to implement the save() method. It just does some validation before adding the current node selections to the savedSelections array:

public save() {
  this.errMsg = '';
  const saveName = this.saveNameRef.nativeElement.value.trim();
  if (saveName === '') {
    this.errMsg = 'Please provide a save name.';
    this.saveNameRef.nativeElement.focus();
  } else {
    this.savedSelections.push({
      name: this.sanitizer.sanitize(SecurityContext.HTML, saveName),
      selections: this.saveSelectedNodes(this.dataSource.data)
    });
  }
}

The sanitize() method is provided by the DomSanitizer that is injected via the constructor:

constructor(private sanitizer: DomSanitizer) {
  // ...
}

It cleans up the save name so that it is fit for inserting into the DOM.

The selections themselves are collected by the recursive saveSelectedNodes() method. Being a recursive method, it follows the template that was introduced earlier. You can see the recursive call where it passes the node’s children along:

private saveSelectedNodes(vehicleNodes: VehicleNode[]): VehicleSelection[] {
  let vehicleSelections = [] as VehicleSelection[];
  vehicleNodes.forEach(node => {
    if (node.selected || node.indeterminate) { 
      const vehicleSelection: VehicleSelection = { id: node.id };
      if (node.children) {
        vehicleSelection.children = this.saveSelectedNodes(node.children);
      }
      vehicleSelections.push(vehicleSelection);
    }
  });
  return vehicleSelections;
}

If we add a console.log() just before each vehicleSelection is pushed onto the vehicleSelections array, we can observe the progress as the method iterates over each node:

Save Console Log

 

It works its way from the leaf node on up to each root level entry.

Going Forward with DOM Tree Structures

There is a demo of our application that includes the save functionality. In the next installment, we will add the code to restore saved selections. You can read the next installment here: Loading Saved Nodes in Angular.

Read more Angular web development tutorials.

Rob Gravelle
Rob Gravelle
Rob Gravelle resides in Ottawa, Canada, and has been an IT guru for over 20 years. In that time, Rob has built systems for intelligence-related organizations such as Canada Border Services and various commercial businesses. In his spare time, Rob has become an accomplished music artist with several CDs and digital releases to his credit.

Popular Articles

Featured