How to iterate an array of objects recursively in TypeScript/Javascript

Question

I have an array with objects that contains two properties: target and source. Moreover, I have a starting source.

Now what I need to start with starting source and find a target from the array. After finding the target, that value becomes source again find a target from that array. It should run recursively until target returned as undefined.

What is the efficient way to do this?

I have implemented this problem as followed. Some short and crisp code suggestion is required.

let result = new Array();
// input
    const a = [
      { source: '2', target: '3' },
      { source: '1', target: '2' },
      { source: '3', target: '4' },
      { source: '4', target: '5' }
    ];
    const startSource = '1';
    result.push(startSource);
   // recursive function
    this.findTarget(startSource, a);
    console.log(result);

Following is the recursive function

 public findTarget(s: string, a: Sequence[]): any {
    let obj = a.find(i => i.source === s);
    if (obj) {
      this.result.push(obj.target);
      return this.findTarget(obj.target, a);
    } else {
      return;
    }
  }

Answer 1

You could create an hashmap or a plain object where the key is the source and the value is the target. This will also avoid needing the recursive approach, since you really just need to process a chain until it's finished.

From that map, you could collect all values until map[nextSource] is undefined.

The below approach does exactly that and takes advantage of function generators to yield the values found.

This should be the most efficient way, since creating the lookup once and checking whether a key exists has O(1) complexity, while applying find for each iteration has an higher complexity (not sure how to calculate it properly, but it should be O(n) or O(n^2) complexity).

If you don't want to, you can avoid using function generators and just collect the result and return it. I've decided to use them because I feel comfortable with their syntax and I like the fact that they are extremely easy to maintain.

SIDE NOTE: in your sample code, you're firstly pushing a source, then some targets. Since i'm not sure which you need to collect, I'm collecting sources. If you need targets, just change yield startSourceValue; to yield reverseMap[startSourceValue];

Below is the working code.

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function* chainSources(array, targetKey, sourceKey, startSourceValue) {
  // Build an object where the [key] is the source property value and the [value] is the target property value.
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});
  
  // Keep chaining the [target] value of initial [source] key until undefined
  while (reverseMap[startSourceValue] !== undefined) {
    yield startSourceValue;
    startSourceValue = reverseMap[startSourceValue];
  }
  return;
}

// For..of usage
for (let target of chainSources(a, 'target', 'source', '1')) {
  console.log(target);
}

// Spread usage.
const result = [...chainSources(a, 'target', 'source', '1')];

console.log(result);

Same solution without function generators:

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function chainSources(array, targetKey, sourceKey, startSourceValue) {
  const res = [];
  // Build an object where the [key] is the source property value and the [value] is the target property value.
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});
  
  // Keep chaining the [target] value of initial [source] key until undefined
  while (reverseMap[startSourceValue] !== undefined) {
    res.push(startSourceValue);
    startSourceValue = reverseMap[startSourceValue];
  }
  return res;
}

const result = chainSources(a, 'target', 'source', '1');

console.log(result);